資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將兩個字串變成字謎的最小步數
假設我們有兩個大小相同的字串 s 和 t。在一步操作中，我們可以選擇 t 的任何字元並將其替換為另一個字元。我們需要找到使 t 成為 s 的字謎所需的最小步數。注意：字串的字謎是指包含相同字元但順序不同（或相同）的字串。
因此，如果輸入類似於 -“yxy” 和“xyx”，則輸出將為 1，因為只需要替換一個字元。
為了解決這個問題，我們將遵循以下步驟 -
n := s 中字元的大小
建立一個對映 m，並用 s 中存在的每個字元的頻率填充它，建立一個對映 m2，並用 t 中存在的每個字元的頻率填充它
ret := n
對於 m 中的每個鍵值對 it
x := it 的值和 m2[it 的值] 的值的最小值
將 ret 減少 1
返回 ret
示例（C++）
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSteps(string s, string t) {
int n = s.size();
map <char, int> m1;
for(int i = 0; i < s.size(); i++){
m1[s[i]]++;
}
int ret = n;
map <char, int> m2;
for(int i = 0; i < t.size(); i++){
m2[t[i]]++;
}
map <char, int> :: iterator it = m1.begin();
while(it != m1.end()){
//cout << it->first << " " << it->second << " " << m2[it->first] << endl;
int x = min(it->second, m2[it->first]);
ret -= x;
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.minSteps("yxy", "xyx"));
}輸入
"yxy" "xyx"
輸出
1
更新於: 2020-04-29
216 次檢視
廣告