对不起,怪我太弱了,这题不会写。
看看官方的题解吧。
题目描述
给定一个字符串S,检查是否能重新排布其中的字母,使得两相邻的字符不同。
若可行,输出任意可行的结果。若不可行,返回空字符串。
样例
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在[1, 500]区间内。
思路
假设字符串的长度为n,当n是偶数时,有n/2个偶数下标和n/2个奇数下标,因此每个字母的出现次数都不能超过n/2次,否则出现次数最多的字母一定会出现相邻。
当n是奇数时,由于共有(n+1)/2个偶数下标,因此每个字母的出现次数都不能超过(n+1)/2次,否则出现次数最多的字母一定会出现相邻。
由于当n是偶数时,在整数除法下满n/2和(n+1)/2相等,因此可以合并n是偶数与n是奇数的情况:如果可以重新排布成相邻的字母都不相同的字符串,每个字母最多出现(n+1)/2次。
因此首先遍历字符串并统计每个字母的出现次数,如果存在一个字母的出现次数大于(n+1)/2,则无法重新排布字母使得相邻的字母都不相同,返回空字符串。如果所有字母的出现次数都不超过(n+1)/2,则考虑如何重新排布字母。
然后维护最大堆存储字母,堆顶元素为出现次数最多的字母。首先统计每个字母的出现次数,然后将出现次数大于0的字母加入最大堆。
当堆的元素个数大于1时每次取出两个字母构建新的字符串,然后将两个字母的出现的次数减一,如果出现次数还是大于0再继续加入到堆中。由于堆中的元素都是不同的,因此取出的两个字母一定不同,不会出现两个相同字母相邻的情况。
如果最大堆变成空,则已经完成字符串的重构。如果最大堆剩下1个元素,则取出最后一个字母,拼接到重构的字符串。
最后返回拼接完成的字符串即可。
C++ 代码
class Solution {
public:
string reorganizeString(string S) {
if(S.size() < 2)
return S;
vector<int> v(26, 0);
int maxCount = 0;
for(int i = 0; i < S.size(); i ++) // 统计每个字母的个数同时找出出现次数最多的次数
{
v[S[i] - 'a'] ++;
maxCount = max(maxCount, v[S[i] - 'a']);
}
if(maxCount > (S.size() + 1) / 2) // 如果最大出现次数大于(n + 1) / 2 则直接返回空字符串
return "";
auto cmp = [&](const char& letter1, const char& letter2) { // 定义比较函数,根据字母出现的次数排序
return v[letter1 - 'a'] < v[letter2 - 'a'];
};
priority_queue<char, vector<char>, decltype(cmp)> q{cmp}; // 利用优先队列定义大根堆
for(char i = 'a'; i <= 'z'; i ++) // 存储出现过的每个字母
if(v[i - 'a'] > 0)
q.push(i);
string s = "";
while(q.size() > 1)
{
char letter1 = q.top(); q.pop(); // 取出堆中的两个字母
char letter2 = q.top(); q.pop();
s += letter1, s += letter2;
v[letter1 - 'a'] --, v[letter2 - 'a'] --; // 出现次数减一
if(v[letter1 - 'a'] > 0) // 如果出现次数不为零,继续加入到堆中
q.push(letter1);
if(v[letter2 - 'a'] > 0)
q.push(letter2);
}
if(q.size() > 0)
s += q.top();
return s;
}
};
您好!感谢分享。
请问您的这个代码 如下这个部分为什么不会出现相同字母相邻的可能?
假设最大堆是 a-2 b-2 c-1 , 第一次取出 ab 得到 substring “ab”, 因为出现次数不为零所以a-1 b-1 加回最大堆 由于
cmp
只定义和字母count相关, 所以加回之后 最大堆是 b-1 a-1 c-1而不是 a-1 b-1 c-1 那么这次取出的subtring就是”ba” 加上之前的”ab” 得到 “abba”了。
朋友你好,感谢你观看我的题解。
在题解中cmp函数的定义是严格小于才会进行排序。所以加回之后大根堆是c-1 a-1 b-1。所以最后不会出现相同的字母在一起的情况。
可以运行下面的代码进行验证。
非常感谢! 很清楚!
谢谢兄弟的支持