数据结构
网络
关系数据库管理系统 (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 次浏览
广告