LeetCode767. Reorganize String

1、题目链接

https://leetcode.com/problems/reorganize-string/

2、解题思路

这道题的意思是说给你一个字符串（字符串里面可能会有相同的字符），让你检查这个字符串能不能被重新排列，使得字符串中的每两个相邻的字符都不一样，如果可以，则返回其中任意一种结果，否则返回空字符串。我们来看看，什么样的情况下会出现被排列之后的字符串一定会有相邻字符串相同的情况，不难想象出，当字符串中某一种字符的个数大于整个字符串长度一半的时候，这时候是肯定会有相同且相邻的情况发生，那么这样的话就得计算一下字符出现的次数了，就像我很早之前说过的一样，遇到这种字符串的题十有八九是要建立一个count数组，来计算字符出现的次数；排除完了接下来我们要怎么做呢？接下来的情况就是一定能排列出的情况了，大家想一想，如果每次我们从字符串中取出出现次数最多和第二多的字符用来生成一个新的字符串，这样子的话就可以保证不会有相邻且相同的字符了，那么这个地方肯定需要一个排序，根据字符出现的次数进行降序排列，然后每次取两两种出来(判断是否还有两种)，方法一中是每次取完都需要进行一次排序操作，方法二种是维护一个优先队列，让这个优先队列里面的对象一直都是按照count从大到小进行排序的。

3、代码

解法1：

class Solution {
    public String reorganizeString(String S) {
        StringBuilder result = new StringBuilder();
        int[] countChar = new int[26];
        List<Letter> letterList = new ArrayList<>();
        for (int i = 0; i < S.length(); i++) {
            countChar[S.charAt(i) - 97]++;
        }
        for (int i = 0; i < countChar.length; i++) {
            if (countChar[i] > (S.length() + 1) / 2) {
                return "";
            }
            if (countChar[i] > 0) {
                letterList.add(new Letter(countChar[i], (char) (i + 97)));
            }
        }
        sort(letterList);  //按照count从大到小排序
        while (letterList.get(0).count  > 0) {
            result.append(letterList.get(0).letter);
            letterList.get(0).count--;
            if (letterList.get(1).count > 0) {
                result.append(letterList.get(1).letter);
                letterList.get(1).count--;
            }
            sort(letterList);  //因为值已经发生变化，所以需要再进行一次排序
        }

        return result.toString();
    }
    
    public void sort(List<Letter> letterList) {
        Collections.sort(letterList, new Comparator<Letter>() {
            @Override
            public int compare(Letter o1, Letter o2) {
                return o2.count - o1.count;
            }
        });
    }
    
    class Letter {
        int count;
        char letter;
        public Letter(int count, char letter) {
            this.count = count;
            this.letter = letter;
        }
    }
}

解法2：

public String reorganizeString(String S) {
    StringBuilder result = new StringBuilder();
    int[] countChar = new int[26];
    for (int i = 0; i < S.length(); i++) {
        countChar[S.charAt(i) - 97]++;
    }
    // 维护一个优先队列，使得队列中的对象按照count从大到小排序
    PriorityQueue<Letter> queue = new PriorityQueue<>(new Comparator<Letter>() {
        @Override
        public int compare(Letter o1, Letter o2) {
            return o2.count - o1.count;
        }
    });
    for (int i = 0; i < countChar.length; i++) {
        if (countChar[i] > (S.length() + 1) / 2) {
            return "";
        }
        if (countChar[i] > 0) {
            queue.add(new Letter(countChar[i], (char) (i + 97)));
        }
    }
    while (queue.size() > 0) {
        Letter l1 = queue.poll();
        Letter l2 = queue.poll();
        if (l1.count > 0) {
            result.append(l1.letter);
            l1.count--;
        }
        if (null != l2 && l2.count > 0) {
            result.append(l2.letter);
            l2.count--;
        }
        if (l1.count > 0) {
            queue.add(l1);
        }
        if (null != l2 && l2.count > 0) {
            queue.add(l2);
        }
    }
    return result.toString();
}
class Letter {
    int count;
    char letter;
    public Letter(int count, char letter) {
        this.count = count;
        this.letter = letter;
    }
}

4、结果

QQ20190712-150111@2x.png