leetcode——767.重构字符串
程序员文章站
2024-03-16 16:44:10
...
思路
- 使用hashmap记录字母出现频率
- 如何重排不可行?size()小于2 或 字母的最高出现频率大于length+1/2
- 将hashmap中不为0的元素放入优先队列中,每次取优先队列最高频率的两个字母作组合
代码
class Solution {
public:
string reorganizeString(string s) {
//无法重新排布
if (s.length() < 2)
return s;
//记录字母出现频率
vector<int> counts(26, 0);
int maxCount = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s[i];
counts[c - 'a']++;
//获取最大的出现频率
maxCount = max(maxCount, counts[c - 'a']);
}
//不可行的情况
if (maxCount > (length + 1) / 2)
return "";
//将hashmap进行挑选 压入优先队列
auto cmp = [&](const char& letter1, const char& letter2) {
return counts[letter1 - 'a'] < counts[letter2 - 'a'];
};
priority_queue<char, vector<char>, decltype(cmp)> queue{cmp};
for (char c = 'a'; c <= 'z'; c++) {
if (counts[c - 'a'] > 0) {
queue.push(c);
}
}
//字符串重排
string sb = "";
while (queue.size() > 1) {
//取头两个字母进行组合
char letter1 = queue.top(); queue.pop();
char letter2 = queue.top(); queue.pop();
sb += letter1;
sb += letter2;
//hashmap对应的字母出现频率更新
int index1 = letter1 - 'a', index2 = letter2 - 'a';
counts[index1]--;
counts[index2]--;
//取后出现频率仍大于0 压入栈
if (counts[index1] > 0)
queue.push(letter1);
if (counts[index2] > 0)
queue.push(letter2);
}
//size()为奇数情况下的最后一个元素
if (queue.size() > 0)
sb += queue.top();
return sb;
}
};
上一篇: Cocos Creator加载文本文件
下一篇: Hello Box2D
推荐阅读
-
leetcode 767. 重构字符串
-
leetcode——767.重构字符串
-
每天一道LeetCode-----给定字符串s和字符数组words,在s中找到words出现的位置,words内部字符串顺序无要求
-
LeetCode 151. 翻转字符串里的单词
-
LeetCode[字符串] - #3 Longest Substring Without Repeating Characters 博客分类: LeetCode LeetCodeJavaAlgorithm题解String
-
Leetcode 443: 压缩字符串
-
LeetCode 443. 压缩字符串
-
0519leetcode每日一题(c++)——680. 验证回文字符串 Ⅱ
-
LeetCode:521. Longest Uncommon Subsequence I(找出特殊的子字符串)
-
leetcode-344-反转字符串(java|python)