leetcode.767. 重构字符串——大顶堆

缺乏、安全感 2022-12-25 01:48 98阅读 0赞

### 文章目录 ###

*  767. 重构字符串
 *  代码与思路
 *   *  大顶堆和小顶堆(概念)
     *   *  代码
 *  参考

# 767. 重构字符串 #

给定一个字符串`S`，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
    输出: "aba"

示例 2:

输入: S = "aaab"
    输出: ""

注意:

`S` 只包含小写字母并且长度在`[1, 500]`区间内。

# 代码与思路 #

## 大顶堆和小顶堆(概念) ##

1)**堆排序**是利用堆这种数据结构而设计的一种排序算法，**堆排序**是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。  
2)堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。  
3)每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆  
![在这里插入图片描述][20190815143824703.png_pic_center]  
![在这里插入图片描述][20190815143937539.jpg_pic_center]

### 代码 ###

class Solution { 
        
        /** * 写一个NewChar类，里面包含字母的出现频数，和字母本身。用优先队列PriorityQueue来存储一个一个的NewChar， * 并自己写一个比较器，通过字母的频数降序排列，即构建一个大顶堆。之后两两输出，输出前两个大的， * 然后将它们两个对应的count频率-1，再次放入，继续输出…… * * 这样输出是为了总能有一个字母可以把频率最多的字母隔开，优先队列是为了维持储存NewChar的集合总是可以降序输出。 * * @param S 定一个字符串S * @return 若可行，输出任意可行的结果。若不可行，返回空字符串。 */
        public String reorganizeString(String S) { 
            //整理好各个字母对应出现的频率
            int[] counts = new int[26];
            for (int i = 0; i < S.length(); i++) { 
                counts[S.charAt(i) - 'a']++;
            }
            //定义大顶堆规则
            PriorityQueue<NewChar> pq = new PriorityQueue<>(26,(o1,o2)->o2.count-o1.count);
            //构建大顶堆
            for (int i = 0; i < 26; i++) { 
                //判断重构是否可行，counts[i] <= (S.length() + 1) / 2)---某个字母过半就不能重构
                if (counts[i] > 0 && counts[i] <= (S.length() + 1) / 2) { 
                    //可以重构，就往大顶堆里面塞对象
                    pq.add(new NewChar(counts[i], (char) (i + 'a')));
                } else if (counts[i] > (S.length() + 1) / 2) { 
                    return "";
                }
            }
            //由大顶堆重构字符串
            StringBuilder str = new StringBuilder();
    
            while (pq.size() > 1) { //最后剩下一个字符或者一个不剩，终止
                //拿出来频率老大和老二
                NewChar c1 = pq.poll();
                NewChar c2 = pq.poll();
    
                str.append(c1.letter);
                str.append(c2.letter);
    
                if (--c1.count > 0) pq.add(c1);
                if (--c2.count > 0) pq.add(c2);
            }
            //若剩下一个，特殊处理；一个不剩正好，美滋滋
            if (pq.size() > 0)
                str.append(pq.poll().letter);
    
            return str.toString();
        }
    
        /** * 自己根据数据特点搞个对象 */
        static class NewChar { 
            int count;//出现的频率
            char letter;//字母
    
            NewChar(int count, char letter) { 
                this.count = count;
                this.letter = letter;
            }
        }
    
        /** * 创建PriorityQueue的时候一定要写一个比较器Comparator，因为NewChar是自己写的一个类， * 不写比较器的话程序自己不知道该如何排序，从而会报错： * * cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpCom */
    }
    //作者:默南茶馆有咖啡

说明`PriorityQueue<NewChar> pq = new PriorityQueue<>(26,(o1,o2)->o2.count-o1.count);`是下面代码的JAVA8 lambda写法。

//定义大顶堆规则
            PriorityQueue<NewChar> pq = new PriorityQueue<>(26, new Comparator<NewChar>() { 
                //重写比较规则 （后面对象 - 前面对象）为大顶堆
    
                /** * 拿过来api说 * @param o1 the first object to be compared. * @param o2 the second object to be compared. * @return a negative integer, zero, or a positive integer as the * first argument is less than, equal to, or greater than the * second. */
                @Override
                public int compare(NewChar o1, NewChar o2) { 
                    //基于出现频率的比较
                    //默认是小顶堆，重写为大顶堆
                    return o2.count - o1.count;
                }
            });

# 参考 #

*  大小堆的一些概念  
    [347.前k个高频元素——最小堆的运用][347._k]  
    [java-数据结构-大顶堆和小顶堆][java-_-]  
    [java 8 lambda 实现 Comparator][java 8 lambda _ Comparator]
 *  大佬对Top k系列问题的总结  
    [“Top” k - 1: leetcode 215][Top_ k - 1_ leetcode 215]  
    [“Top” k - 2: 面试题17.14][Top_ k - 2_ _17.14]  
    [“Top” k - 3: leetcode 973][Top_ k - 3_ leetcode 973]  
    [“Top” k - 4: leetcode 1167][Top_ k - 4_ leetcode 1167]  
    [“Top” k - 5: leetcode 347][Top_ k - 5_ leetcode 347]  
    [“Top” k - 6: leetcode 451][Top_ k - 6_ leetcode 451]  
    [“Top” k - 7: leetcode 767][Top_ k - 7_ leetcode 767]

[20190815143824703.png_pic_center]: /images/20221120/8c34a1d0b5a0460889359b7c559b0a1e.png
[20190815143937539.jpg_pic_center]: /images/20221120/6476c45d10284fdfa07c8e8b16953338.png
[347._k]: https://blog.csdn.net/e891377/article/details/108447612
[java-_-]: https://blog.csdn.net/e891377/article/details/99635372
[java 8 lambda _ Comparator]: https://blog.csdn.net/qq_37645385/article/details/89071634
[Top_ k - 1_ leetcode 215]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/java-top-k-1-by-donoghl-2/
[Top_ k - 2_ _17.14]: https://leetcode-cn.com/problems/smallest-k-lcci/solution/java-top-k-2-by-donoghl/
[Top_ k - 3_ leetcode 973]: https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/java-top-k-3-by-donoghl/
[Top_ k - 4_ leetcode 1167]: https://leetcode-cn.com/problems/minimum-cost-to-connect-sticks/solution/java-top-k-4-by-donoghl/
[Top_ k - 5_ leetcode 347]: https://leetcode-cn.com/problems/top-k-frequent-elements/solution/java-top-k-5-by-donoghl/
[Top_ k - 6_ leetcode 451]: https://leetcode-cn.com/problems/sort-characters-by-frequency/solution/java-top-k-5-by-donoghl-2/
[Top_ k - 7_ leetcode 767]: https://leetcode-cn.com/problems/reorganize-string/solution/java-top-k-7-by-donoghl/