想了解更多數(shù)據(jù)結(jié)構(gòu)以及算法題，可以關(guān)注微信公眾號(hào)“數(shù)據(jù)結(jié)構(gòu)和算法”，每天一題為你精彩解答。

問(wèn)題描述

給定一個(gè)字符串S，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。

若可行，輸出任意可行的結(jié)果。若不可行，返回空字符串。

示例 1:

輸入: S = “aab”

輸出: “aba”

示例 2:

輸入: S = “aaab”

輸出: “”

注意:

• S 只包含小寫(xiě)字母并且長(zhǎng)度在[1, 500]區(qū)間內(nèi)。

問(wèn)題分析

這題是讓重新排布字符串S中的字符，讓任何兩個(gè)相鄰的字符都不相同，如果能做到就返回排布后的字符串，如果做不到就返回空字符串。

如果要使得兩相鄰的字符不同，那么出現(xiàn)次數(shù)最多的那個(gè)數(shù)的數(shù)量必須滿(mǎn)足下面條件，如下圖所示，比如下面的a是出現(xiàn)次數(shù)最多的

這個(gè)時(shí)候a的數(shù)量已經(jīng)達(dá)到了臨界值，如果再多一個(gè)a，那么至少有兩個(gè)a是相鄰的。所以這里出現(xiàn)次數(shù)最多的那個(gè)字符數(shù)量的臨界值是threshold = (length + 1) >> 1(其中 length 是字符串的長(zhǎng)度)

如果能使得兩相鄰的字符不同，我們可以先把出現(xiàn)次數(shù)最多的那個(gè)字符放到新數(shù)組下標(biāo)為偶數(shù)的位置上，也就是從數(shù)組的第一個(gè)位置開(kāi)始放，放完之后在用其他的字符填充數(shù)組剩下的下標(biāo)為偶數(shù)的位置，如果下標(biāo)為偶數(shù)的位置都填滿(mǎn)了，我們就從下標(biāo)為1開(kāi)始，也就是數(shù)組的第2個(gè)位置開(kāi)始，填下標(biāo)為奇數(shù)的位置。

注意這里能不能先把出現(xiàn)次數(shù)最多的字符放到字符串下標(biāo)為奇數(shù)的位置呢，當(dāng)然是不可以的。比如我們上面舉的例子abacaba本來(lái)是可以滿(mǎn)足的，如果放到下標(biāo)為奇數(shù)的位置，最后一個(gè) a 就沒(méi)法放了，除非放到最前面，那又變成了放到下標(biāo)為偶數(shù)的位置了。

代碼如下

public String reorganizeString(String S) { //把字符串S轉(zhuǎn)化為字符數(shù)組 char[] alphabetArr = S.toCharArray(); //記錄每個(gè)字符出現(xiàn)的次數(shù) int[] alphabetCount = new int[26]; //字符串的長(zhǎng)度 int length = S.length(); int max = 0, alphabet = 0, threshold = (length + 1) >> 1; //找出出現(xiàn)次數(shù)最多的那個(gè)字符 for (int i = 0; i < length; i++) { alphabetCount[alphabetArr[i] - 'a']++; if (alphabetCount[alphabetArr[i] - 'a'] > max) { max = alphabetCount[alphabetArr[i] - 'a']; alphabet = alphabetArr[i] - 'a'; //如果出現(xiàn)次數(shù)最多的那個(gè)字符的數(shù)量大于閾值， // 說(shuō)明他不能使得兩相鄰的字符不同， // 直接返回空字符串即可 if (max > threshold) return ""; } } //到這一步說(shuō)明他可以使得兩相鄰的字符不同， // 我們隨便返回一個(gè)結(jié)果，res就是返回 //結(jié)果的數(shù)組形式，最后會(huì)再轉(zhuǎn)化為字符串的 char[] res = new char[length]; int index = 0; //先把出現(xiàn)次數(shù)最多的字符存儲(chǔ)在數(shù)組下標(biāo)為偶數(shù)的位置上 while (alphabetCount[alphabet]-- > 0) { res[index] = (char) (alphabet + 'a'); index += 2; } //然后再把剩下的字符存儲(chǔ)在其他位置上 for (int i = 0; i < alphabetCount.length; i++) { while (alphabetCount[i]-- > 0) { //如果偶數(shù)位置填完了，我們就讓index從1開(kāi)始， // 填充下標(biāo)為奇數(shù)的位置 if (index >= res.length) { index = 1; } res[index] = (char) (i + 'a'); index += 2; } } return new String(res);}

總結(jié)

這題直接判斷比較簡(jiǎn)單，我們只需要統(tǒng)計(jì)出出現(xiàn)次數(shù)最多的字符即可。但這題還要返回結(jié)果，所以最簡(jiǎn)單的方式就是把出現(xiàn)次數(shù)最多的字符從數(shù)組的第一個(gè)位置開(kāi)始放，每隔一個(gè)放一次。放完之后再用其他的字符從后面接著放，也是每隔一個(gè)，如果超出數(shù)組之后再?gòu)臄?shù)組的第2個(gè)位置開(kāi)始放，也是每隔一個(gè)，這樣就能保證結(jié)果一定不會(huì)出錯(cuò)，并且也少了很多的判斷。

總結(jié)

以上是生活随笔為你收集整理的找出一个字符串中出现次数最多的字_487，重构字符串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。