C++刷LeetCode（767. 重构字符串）【字符串】**

糖逗

题目描述：

1. 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
   
2. 
   
3. 若可行，输出任意可行的结果。若不可行，返回空字符串。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: S = "aab"
   
8. 输出: "aba"
   
9. 示例 2:
   
10. 
    
11. 输入: S = "aaab"
    
12. 输出: ""
    
13. 注意:
    
14. 
    
15. S 只包含小写字母并且长度在[1, 500]区间内。

复制代码

1. class Solution {
   
2. public:
   
3.     string reorganizeString(string S) {
   
4.         //1.选取出现最大频次的字符串作为基准字符串
   
5.         vector<int> store(26);
   
6.         for(auto cha : S)store[cha - 'a']++;
   
7.         int len = S.size();
   
8.         int max_num = *max_element(store.begin(), store.end());
   
9.         int max_index = max_element(store.begin(), store.end()) - store.begin();
   
10.         //最大字符的频次超过半数的就直接返回“”表示不能实现
    
11.         if(len % 2 == 0 && max_num > len / 2)return "";
    
12.         else if(len % 2 != 0 && max_num > (len + 1)/2)return "";
    
13.         string res(max_num, max_index + 'a');
    
14.         int temp1 = 0;//表示26个字母中的第几个字母
    
15.         int temp2 = 1;//表示在temp2位置前插入(位置从0开始)
    
16.         while(temp1 < 26){
    
17.             if(temp1 == max_index){
    
18.                 temp1 ++;
    
19.                 continue;
    
20.             }
    
21.             while(store[temp1] != 0){
    
22.                 store[temp1]--;
    
23.                 res.insert(temp2, 1, 'a' + temp1);
    
24.                 temp2 = (temp2 + 2) % res.size();//隔一个字符一插入
    
25.             }
    
26.             temp1++;
    
27.         }
    
28.         return res;
    
29.     }
    
30. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -bi-ji-767-by-ae2a/

糖逗

之后再看一遍