Daily LeetCode – day0010 0761. Special Binary String

// 0761. Special Binary String
class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() < 3) {
            return s;
        }
        int prefixSum = 0;
        int processed = 0;
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++prefixSum;
            } else {
                --prefixSum;
                if (prefixSum == 0) {
                    pq.offer("1" + makeLargestSpecial(s.substring(processed + 1, i)) + "0");
                    processed = i + 1;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            sb.append(pq.poll());
        }
        return sb.toString();
    }
}
学习笔记:
这是一道很困难的字符串题,需要用到分治思想递归调用。
找到每一个最大的1和0包的部分,再内部排序,排完序之后整体排序。
看完后会发觉这道题目的精妙。
一开始我用了List和Collections.sort(),String.join()来返回,这样时间是3ms。
我觉得可能是排序消耗比较花时间吧,就改用了PriorityQueue,用了之后就报错了,这里有一个坑,就是使用 增强for循环 和 迭代器遍历 是不可以按正确顺序遍历PriorityQueue的,所以得用记录size后的普通for循环 或者 while循环来遍历。
这道题的PriorityQueue是个最大堆,可以使用Comparator,也可以使用lambda表达式。
(o1, o2) -> {return o2.compareTo(o1);}


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注