LeetCode 767. 重构字符串

1、题目

重构字符串 - 力扣（LeetCode） https://leetcode-cn.com/problems/reorganize-string/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

2、题解

这个题目其实关键是在于数量最多的字符，如果它的数量超过一半就不行，如果不超过一般就可以；交叉存放即可。所以可以把数量最多的这个字符想象成放在满二叉树的所有左子树节点上，其余的依次放在右子树节点上即可。

3、代码

class Solution {
        public String reorganizeString(String S) {
            //1、得到数量最多的字符，如果数量超过一半就不行，如果不超过一般就可以；交叉存放即可
            //将每个字母的数量放进对应的位置
            int[] zimuCount = new int[26];
            String s = "";
            int lenth = S.length();

            int maxNum = 0;//最大的数量
            int index = 0;//最大的数量对应的下标
            int relative;//当下字符对于‘a’的相对位置。

            //最后的结果
            char[] res = new char[lenth];

            //统计得到26个字母每一个的数量
            for(int i= 0; i< lenth;i++){
                relative = (int)(S.charAt(i) - 'a');//当下字符对于‘a’的相对位置。
                zimuCount[relative]++;//relative这个位置的字母的数量
                if(zimuCount[relative]>maxNum){
                    maxNum = zimuCount[relative];
                    index = relative;
                }
            }
            //开始往res里面放置数据
            //n是放置的位置
            int n = 0;
            //如果数量超过一半就不行
            if(maxNum <= (lenth+1)/2){
                //放置第一部分，最多的字母部分
                for(int k = 0;k<zimuCount[index];k++){
                    res[n] = (char)(index + 'a');
                    n +=2;
                }
                zimuCount[index] = 0;
                //放置第二部分
                for(int i = 0 ; i < 26; i++) {
                    int c = zimuCount[i];
                    //把c消耗完了再到下一个。
                    while(c > 0 ) {
                        if(n >= lenth){
                            n = 1;
                        }
                        res[n] = (char)(i + 'a');
                        n += 2;
                        c --;
                    }
                }
                s = new String(res);
                return s;
            }else{
                return s;
            }

        }
    }

4、执行结果

image.png