給定一個字串S，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同，
若可行，輸出任意可行的結果，若不可行，回傳空字串，
示例 1:
輸入: S = "aab"
輸出: "aba"
示例 2:
輸入: S = "aaab"
輸出: ""
注意:
S 只包含小寫字母并且長度在[1, 500]區間內，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reorganize-string
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
對字串進行統計每一個字符出現的次數，
第一部分：先判斷能否重新排布，當一個字母出現的個數比字串長度一半還要多時就無法重新排布；
第二部分：進行重新排列，最長為500個，其實就可以開辟一個陣列（相當于挖好坑，等下把蘿卜埋下去就可以了），把同一字符間隔排序就好了：
1、以字符出現的個數多少來決定先排布哪個字符，舉個栗子：aaaiij,如果不先排a，先把i和j用了，iji，就還剩下兩個a，就無法重新排布，
2、先排0、2、4、6、8...位置上的，當已經填滿一半時就可以排1、3、5、7...
舉個栗子：aaaabbbbcccc
先排第一趟0、2、4、6、8、10：a_a_a_a_b_b_
接下來從1、3、5、7、9：ababacacbcbc
就完成了字串的重新排列，
class Solution {
public:
string reorganizeString(string S) {
int num[30],l,p1,p2,temp[505],k,flag;
string res="";
fill(num,num+30,0);
for (int i=0;i<S.length();i++){
num[S[i]-'a']++;//對每一個字符進行統計出現的個數
}
for (int i=0;i<26;i++){
if (num[i]>=(S.length()+1)/2+1){//當有字符出現次數大于一般就判定為無法重新排列
return "";
}
}
l=0;//代表已完成重新排列的字符個數
p1 = -1;//記錄當前填入的字符（找到的出現的次數的字符）
k=0;//當前填入到臨時陣列的下標
flag=0;//用與代表還沒開始第二趟
while(l<S.length()){
if (l>=((S.length()+1)/2)&&flag==0){//當已填完一般的字符時，開始第二趟
k=1;
flag=1;
}
if (p1==-1||num[p1]==0){//當前指向的字符已全部完成了重新排列，需要找尋下一個字符
for (int i=0;i<26;i++){
if (num[i]!=0){
p1=i;
break;
}
}
for (int i=0;i<26;i++){//找到出現次數最多的字符
if (num[i]>num[p1]){
p1 = i;
}
}
}
temp[k]=p1;//填入該字符到臨時陣列中去
k+=2;//間隔填入
l++;
num[p1]--;
}
for (int i=0;i<S.length();i++){//按陣列的排列，重新獲得字串
res+=('a'+temp[i]);
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228741.html
標籤：其他
上一篇：qsort的cmp函式理解