資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++自定義字串排序
假設我們有兩個字串S和T，它們都由小寫字母組成。在S中，每個字母最多出現一次。S之前按某種自定義順序排序過。我們需要對T的字元進行排列，使其與S排序的順序匹配。更具體地說，如果x在S中出現在y之前，那麼x將在返回的字串中出現在y之前。
例如，如果S = “cba”而T = “abcd”，則輸出將是“cbad”。因為“a”、“b”、“c”出現在S中，所以“a”、“b”、“c”的順序應該是“c”、“b”和“a”。由於“d”沒有出現在S中，它可以在T中的任何位置。“dcba”、“cdba”、“cbda”也是有效的輸出。
為了解決這個問題，我們將遵循以下步驟：
將ret設定為空字串
定義一個map m，並將T中每個字元的頻率儲存到m中
對於i從0到S的長度減1
x := S[i]
對於j從0到m[x]減1
ret := ret + x
m[x] := 0
對於m中的每個鍵值對it：
如果it的值 > 0，則
對於i從0到it的值減1
ret := ret連線it的鍵
返回ret
示例(C++)
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string customSortString(string S, string T) {
string ret = "";
unordered_map <char, int> m;
for(int i = 0; i < T.size(); i++){
m[T[i]]++;
}
for(int i = 0; i < S.size(); i++){
char x = S[i];
for(int j = 0; j < m[x]; j++){
ret += x;
}
m[x] = 0;
}
unordered_map <char, int> :: iterator it = m.begin();
while(it != m.end()){
if(it->second > 0){
for(int i = 0; i < it->second; i++)ret += it->first;
}
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.customSortString("cba", "abcd"));
}輸入
"cba" "abcd"
輸出
cbad
更新於：2020年5月2日
438 次瀏覽
廣告