資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學將字串1中的字元轉換為字串2中存在的字元，方法是按字典順序遞增或遞減。
在這個問題中，程式設計師需要透過執行增量或減量操作來使str1的所有字元等於str2的任何字元。此外，我們可以迴圈遞增或遞減。這意味著'z' + 1 == 'a'，而'a' – 1 == 'z'。
我們可以透過找到使str1字串的字元等於str2字串的任何字元的最小成本來解決這個問題。對於每個字元，我們可以找到所需的最小操作次數並將它們全部相加。
問題陳述 – 我們得到了兩個名為str1和str2的字串。str1的大小為N，str2的大小為M。此外，給定的條件是N <= M或N > M。這兩個字串僅包含小寫字母字元。任務是，我們需要透過增量或減量操作使str1的所有字元等於str2的任何字元。我們需要找到使str1的所有字元等於str2的任何字元所需的最小操作次數。
示例
輸入
str1 = "aedc", str2 = "db";
輸出
3
解釋
我們可以使'a'等於'b'，其代價是1。
我們可以使'e'等於'd'；其代價是1。
'd'已經存在於str2中，所以代價是0。
我們可以使'c'等於b或d；代價將是1。
因此，所需的總代價或所需的操作次數為3。
輸入
str1 = "mwerd", str2 = "dermw";
輸出
0
解釋 – str1的所有字元都存在於str2中。因此，所需的操作次數等於零。
輸入
str1 = "bdfhjlnp", str2 = "acegikmo";
輸出
8
解釋 – 我們可以透過將字元遞增或遞減1來使str1的每個字元等於str2的任何字元。例如，'b' -> 'a'，'d' -> 'c'或'd' -> 'e'等等。
方法1
我們將取str1字串的任何字元，並透過執行增量或減量操作使其等於str2的每個字元。之後，我們將找到str1每個字元的最小成本並將它們全部相加。
讓我們瞭解使一個字元等於另一個字元的兩種方法。
將字元'a'轉換為'e'。
透過遞增，我們需要4次操作才能使'a'等於'e'。
透過遞減操作，我們需要26 – 4 = 22次操作。
這裡，4是最小值，所以我們將考慮它。
將字元'a'轉換為'y'。
透過遞增，我們需要24次操作。
透過遞減，我們需要2次操作。
因此，所需的最小操作次數為4。
演算法
步驟1 – 定義名為'str2Chars'的無序雜湊對映來儲存str2字串中字元的頻率。
步驟2 – 遍歷字串並在雜湊對映中更新每個字元的頻率。
步驟3 – 定義'count'變數來儲存所需的最小操作次數。
步驟4 – 開始遍歷字串1。在迴圈中，用最大整數值初始化minMoves變數來儲存使第p個字元等於str2的任何字元所需的最小操作次數。
步驟5 – 使用迴圈進行1到26次迭代。透過從str1[p]中減去'a'來獲取0到25之間的字元值。
步驟6 – 如果當前字元存在於雜湊對映中，則將零賦值給minMoves變數並中斷迴圈。
步驟7 – 否則，如果'a' + q字元存在於雜湊對映中，我們可以將p字元轉換為'a' + q。
步驟8 – 透過遞增操作獲得使字元等於'a' + q的總操作次數，並將其儲存到leftMin變數中。
步驟9 – 同樣，找到透過遞減操作使字元等於'a' + q的總操作次數，並將它們儲存到rightMin變數中。
步驟10 – 從'leftMin'和'rightMin'中獲取最小值。此外，從allMoves和minMoves中獲取最小值。
步驟11 – 將minMoves新增到count變數的值中。
步驟12 – 返回'count'值。
示例
#include <bits/stdc++.h>
using namespace std;
int totalOps(string str1, string str2) {
// Map to store all characters of str2
unordered_map<char, int> str2Chars;
// Traverse str2
for (int p = 0; p < str2.size(); p++) {
str2Chars[str2[p]]++;
}
// Store minimum operations
int count = 0;
// Traverse str1
for (int p = 0; p < str1.size(); p++) {
// Total minimum move requires converting one character to another
int minMoves = INT_MAX;
// Calculate required moves
for (int q = 0; q < 26; q++) {
// Get the character value
int char_val = str1[p] - 'a';
// If str2 contains the str1[p]
if (str2Chars[str1[p]] > 0) {
minMoves = 0;
break;
} else if (str2Chars['a' + q] > 0) {
// Find minimum difference between str1[p] and str2[q]
int leftMin = abs(char_val - q);
int RightMin = min((26 - char_val) + q, char_val + (26 - q));
int allMoves = min(leftMin, RightMin);
minMoves = min(minMoves, allMoves);
}
}
// Update minimum operations
count += minMoves;
}
// Return total operations
return count;
}
int main() {
string str1 = "aedc";
string str2 = "db";
cout << "The minimum numbers of operations required to convert str1 to str2 is " << totalOps(str1, str2);
return 0;
}
輸出
The minimum numbers of operations required to convert str1 to str2 is 3
時間複雜度 – O(N*26) ~ O(N)，因為我們遍歷了字串。
空間複雜度 – O(1)，因為我們沒有使用常量空間。
類似地，程式設計師可以嘗試解決我們需要使所有str2等於str1的問題。因此，我們需要從增量或減量操作中獲取最小值，以將str1中第p個索引處的字元轉換為str2中第p個索引處的字元。
65 次檢視
