-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
68 lines (56 loc) · 1.95 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <queue>
#include <iostream>
#include <unordered_map>
using namespace std;
class Solution {
priority_queue<pair<int,char>> helper;
unordered_map<char, int> dict;
public:
string rearrangeString(string s, int k) {
int size = s.size();
string rtn;
// 没有明确k的取值范围,有个case是s="a", k=0... 如果不处理的话下面的操作会超时
//if (k==0) return (size>1)?"":s;//大意了,k=0意味着相同的字符紧挨着也没问题
if (k==0) return s;
// 首先完成统计
for (auto lo : s) {
++dict[lo];
}
// 然后加入到最大堆里面
for (auto & [key, cnt] : dict) {
helper.push({cnt, key});
}
// 最后是构造string,注意跳出条件
while (helper.size()) {
vector<pair<int,char>> tmps;
for (int i = 0; i < k; ++i) {
if (helper.size()) {
// 从堆里面取一个char,然后增加到rtn里面
auto tmp = helper.top(); helper.pop();
rtn.push_back(tmp.second);
if (--tmp.first) tmps.push_back(tmp);
} else {
// 说明出现了不能凑够最短距离k的情况
return (tmps.size())?"":rtn;
}
}
for (auto tmp : tmps) helper.push(tmp);
}// 应该是跳不出while循环的
return rtn;
}
};
int main() {
Solution gua1, gua2, gua3;
// test string
string str, rst;
str = "aaabc";
rst = gua1.rearrangeString(str, 3);
cout << "expect value = \"\", actual value = " << rst.c_str() << endl;
str = "aabbcc";
rst = gua2.rearrangeString(str, 3);
cout << "expect value = \"abcabc\", actual value = " << rst << endl;
str = "aa";
rst = gua3.rearrangeString(str, 0);
cout << "expect value = \"aa\", actual value = " << rst.c_str() << endl;
return 0;
}