本文共 2228 字，大约阅读时间需要 7 分钟。

重新排布字符串的方法

给定一个字符串S，我们需要检查是否能重新排布其中的字母，使得相邻的字符都不相同。如果可以，输出任意一个满足条件的结果；如果不可能，则返回空字符串。

方法思路

为了确定是否可以重新排布字符串，我们需要检查每个字符的出现次数是否超过允许的最大值。根据字符串的长度n，最大允许的出现次数为：

• 当n是偶数时，maxAllowed = n / 2
• 当n是奇数时，maxAllowed = (n + 1) / 2

如果有任何一个字符的出现次数超过maxAllowed，那么就无法重新排布字符串。

如果所有字符的出现次数都在允许范围内，可以使用贪心算法通过最大堆来构造满足条件的字符串。具体步骤如下：

代码实现

import java.util.PriorityQueue;import java.util.Comparator;public class Solution {    public String reorganizeString(String S) {        final int[] alpha = new int[26];        int len = S.length();        for (int i = 0; i < len; i++) {            char ch = S.charAt(i);            alpha[ch - 'a']++;        }        int maxOccur = 0;        for (int i = 0; i < 26; i++) {            if (alpha[i] > maxOccur) {                maxOccur = alpha[i];            }        }        int maxAllowed = (len + 1) / 2;        if (maxOccur > maxAllowed) {            return "";        }        PriorityQueue
   
     queue = new PriorityQueue<>(new Comparator
    
     () {            @Override            public int compare(Character o1, Character o2) {                return alpha[o2 - 'a'] - alpha[o1 - 'a'];            }        });        for (int i = 0; i < 26; i++) {            if (alpha[i] > 0) {                queue.offer((char) ('a' + i));            }        }        StringBuilder result = new StringBuilder();        while (queue.size() > 1) {            char ch1 = queue.poll();            char ch2 = queue.poll();            result.append(ch1);            result.append(ch2);            alpha[ch1 - 'a']--;            alpha[ch2 - 'a']--;            if (alpha[ch1 - 'a'] > 0) {                queue.offer(ch1);            }            if (alpha[ch2 - 'a'] > 0) {                queue.offer(ch2);            }        }        if (queue.size() > 0) {            result.append(queue.poll());        }        return result.toString();    }}
    
   

代码解释

转载地址：http://regyk.baihongyu.com/