C++刷LeetCode（767. 重构字符串）【字符串】**
题目描述：给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在区间内。
class Solution {
public:
string reorganizeString(string S) {
//1.选取出现最大频次的字符串作为基准字符串
vector<int> store(26);
for(auto cha : S)store++;
int len = S.size();
int max_num = *max_element(store.begin(), store.end());
int max_index = max_element(store.begin(), store.end()) - store.begin();
//最大字符的频次超过半数的就直接返回“”表示不能实现
if(len % 2 == 0 && max_num > len / 2)return "";
else if(len % 2 != 0 && max_num > (len + 1)/2)return "";
string res(max_num, max_index + 'a');
int temp1 = 0;//表示26个字母中的第几个字母
int temp2 = 1;//表示在temp2位置前插入(位置从0开始)
while(temp1 < 26){
if(temp1 == max_index){
temp1 ++;
continue;
}
while(store != 0){
store--;
res.insert(temp2, 1, 'a' + temp1);
temp2 = (temp2 + 2) % res.size();//隔一个字符一插入
}
temp1++;
}
return res;
}
};
参考链接：https://leetcode-cn.com/problems/reorganize-string/solution/jing-jing-de-bi-ji-767-by-ae2a/ 之后再看一遍{:10_327:}
页:
[1]