关于后端:刷爆-LeetCode-周赛-339贪心-排序-拓扑排序-平衡二叉树

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。

大家好，我是小彭。

上周末是 LeetCode 第 339 场周赛，你加入了吗？这场周赛笼罩的知识点比拟少，前三题很简略，第四题上难度。

周赛纲要

2609. 最长均衡子字符串（Easy）

• 模仿：$O(n)$

2610. 转换二维数组（Medium）

• 贪婪：$O(n)$

2611. 老鼠和奶酪（Medium）

• 排序 + 贪婪：$O(nlgn)$

2612. 起码翻转操作数（Hard）

• 题解一：拓扑排序 · 超出工夫限度 $O(nk)$
• 题解二：BFS + 均衡二叉树 $O(nlgn)$

2609. 最长均衡子字符串（Easy）

题目地址

https://leetcode.cn/problems/find-the-longest-balanced-substr…

题目形容

给你一个仅由 0 和 1 组成的二进制字符串 s。

如果子字符串中 所有的  0  都在  1  之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是均衡子字符串。请留神，空子字符串也视作均衡子字符串。

返回  s 中最长的均衡子字符串长度。

子字符串是字符串中的一个间断字符序列。

题解（模仿）

简略模拟题。

保护间断 0 的计数 cnt0 和间断 1 的计数 cnt1，并在 cnt0 == cnt1 时更新最长均衡子串长度为 2 * cnt1。另外，在每段 0 的起始地位从新计数。

class Solution {fun findTheLongestBalancedSubstring(s: String): Int {
        var index = 0
        var cnt0 = 0
        var cnt1 = 0
        var ret = 0
        while (index < s.length) {if (s[index] == '0') {
                // 每段 0 的起始地位清零
                if (index > 0 && s[index - 1] == '1') {
                    cnt0 = 0
                    cnt1 = 0
                }
                cnt0++
            } else {cnt1++}
            if (cnt1 <= cnt0) ret = Math.max(ret, cnt1 * 2)
            index++
        }
        return ret
    }
}

复杂度剖析：

• 工夫复杂度：$O(n)$ 其中 $n$ 为 $nums$ 数组的长度；
• 空间复杂度：$O(1)$ 仅应用常数级别变量。

2610. 转换二维数组（Medium）

题目地址

https://leetcode.cn/problems/convert-an-array-into-a-2d-array…

题目形容

给你一个整数数组 nums。请你创立一个满足以下条件的二维数组：

• 二维数组应该 只 蕴含数组 nums 中的元素。
• 二维数组中的每一行都蕴含 不同 的整数。
• 二维数组的行数应尽可能 少。

返回后果数组。如果存在多种答案，则返回其中任何一种。

请留神，二维数组的每一行上能够存在不同数量的元素。

题解（贪婪）

贪婪思路：首先计算每个元素的呈现次数，为了防止同一行的反复，将反复元素从上到下排列到不同行中。

优化：能够在一次遍历中实现，在呈现更大呈现次数时减少一行，在更新元素技术 cnt 后插入到第 cnt – 1 行。

class Solution {fun findMatrix(nums: IntArray): List<List<Int>> {val cnts = IntArray(201)
        val ret = LinkedList<LinkedList<Int>>()
        var maxCnt = 0
        // 计数
        for (num in nums) {
            // 累加
            val curCnt = ++cnts[num]
            // 创立新行
            if (curCnt > maxCnt) {
                maxCnt = curCnt
                ret.add(LinkedList<Int>())
            }
            // 散布
            ret[curCnt - 1].add(num)
        }
        return ret
    }
}

复杂度剖析：

• 工夫复杂度：$O(n)$ 其中 $n$ 为 $nums$ 数组的长度，每个元素拜访一次；
• 空间复杂度：$O(U)$ 计数数组空间。

2611. 老鼠和奶酪（Medium）

题目地址

https://leetcode.cn/problems/mice-and-cheese/

题目形容

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

• 如果第一只老鼠吃掉，则得分为 reward1[i]。
• 如果第二只老鼠吃掉，则得分为 reward2[i]。

给你一个正整数数组 reward1，一个正整数数组 reward2，和一个非负整数 k。

请你返回第一只老鼠恰好吃掉 k 块奶酪的状况下，最大 得分为多少。

题解（排序 + 贪婪）

容易了解：为了使最终得分最大，应该让每只老鼠吃到尽可能大的奶酪。

因为两只老鼠吃的奶酪是互斥关系，因而咱们能够先假如所有奶酪被第一只老鼠食得，而后再筛选 n - k 个奶酪还给第二只老鼠。

那么，对于每个地位 i，将奶酪从第一只老鼠还给第二只老鼠存在差值 diff = reward2[i] - reward1[i]，示意得分的差值为 diff。差值为正得分变大，差值为负得分升高，显然升高越少越好。

因而，咱们的算法是对 diff 排序，将得分升高越大的地位保留给第一只老鼠，其余还给第二只老鼠。

class Solution {fun miceAndCheese(reward1: IntArray, reward2: IntArray, k: Int): Int {
        // 贪婪：优先选择差值最大的地位
        val n = reward1.size
        var ret = 0
        val indexs = Array(n) {it}
        // 升序
        Arrays.sort(indexs) { i1, i2 ->
            (reward2[i1] - reward1[i1]) - (reward2[i2] - reward1[i2])
        }
        for (i in 0 until n) {ret += if (i < k) {reward1[indexs[i]]
            } else {reward2[indexs[i]]
            }
        }
        return ret
    }
}

复杂度剖析：

• 工夫复杂度：$O(nlgn + n)$ 其中 $n$ 为 $nums$ 数组的长度；
• 空间复杂度：$O(n + lgn)$ 索引数组和递归栈空间。

2612. 起码翻转操作数（Hard）

题目地址

https://leetcode.cn/problems/minimum-reverse-operations/

题目形容

给你一个整数 n 和一个在范畴 [0, n - 1] 以内的整数 p，它们示意一个长度为 n 且下标从 0 开始的数组 arr，数组中除了下标为 p 处是 1 以外，其余所有数都是 0。

同时给你一个整数数组 banned，它蕴含数组中的一些地位。banned 中第 i 个地位示意 arr[banned[i]] = 0，题目保障 banned[i] != p。

你能够对 arr 进行 若干次  操作。一次操作中，你抉择大小为 k 的一个  子数组 ，并将它  翻转 。在任何一次翻转操作后，你都须要确保 arr 中惟一的 1 不会达到任何 banned 中的地位。换句话说，arr[banned[i]] 始终  放弃 0。

请你返回一个数组 ans，对于 [0, n - 1] 之间的任意下标 i，ans[i] 是将 1 放到地位 i 处的 起码 ** 翻转操作次数，如果无奈放到地位 i 处，此数为 -1。

• 子数组  指的是一个数组里一段间断  非空 的元素序列。
• 对于所有的 i，ans[i] 相互之间独立计算。
• 将一个数组中的元素 翻转  指的是将数组中的值变成  相同程序。

题解一（拓扑排序 · 超出工夫限度）

剖析 1：对于翻转窗口 [L, R] 中的地位 i，翻转后的下标为 $\frac{L+R}{2} +（\frac{L+R}{2} – i) = L + R – i$

剖析 2：首先地位 p 的翻转次数恒等于 0，而 banned 数组示意的地位翻转次数恒等于 -1。

剖析 3：当地位 i 位于翻转窗口的左半局部时，将翻转到更大地位；当地位 i 位于翻转窗口的右半局部时，将翻转到更小地位；

剖析 4：当初咱们须要剖析地位 i（初始 i 为 0）能够翻转到的地位：

• 状况 1：如果将 i 作为翻转窗口的左右边界，则有：

  • 位于左边界时，翻转后的下标为 i + k - 1；
  • 位于有边界时，翻转后的下标为 i - k + 1。
• 状况 2：如果将 i 放在翻转窗口外部，则所有翻转后的下标正好形成差值为 2 的等差数列。

因而，i 能够翻转的区间为 [i – k + 1, i + k – 1] 中距离 2 的地位（排除 banned 数组），或者了解为奇偶性雷同的下标。

剖析 5：因为翻转窗口有地位限度，会限度翻转：

• 窗口左边界在地位 0 时，且 i 位于翻转窗口的右半局部时（筹备向左翻），则翻转后的地位是 0 + (k - 1) - i = k - 1 - i。因为窗口无奈持续左移，所以小于 k - i - 1 的地位都不可达；
• 同理，窗口右边界位于 n - 1 时，且 i 位于翻转窗口的右边局部时（筹备向右翻），则翻转后的地位是 (n - k) + (n - 1) - i = 2n - k - i - 1。因为窗口无奈持续右移，所以大于 2n - k - i - 1 的地位都不可达。

综上，可得翻转后区间为 [max(i – k + 1, k – i – 1), min(i + k – 1, 2n – k – i – 1)] 中与 i 奇偶性雷同的地位。

至此，容易发现问题能够用拓扑排序（BFS 写法）解决：初始时将 p 地位入队，随后每一轮的翻转次数 + 1，并将该地位入队。

class Solution {fun minReverseOperations(n: Int, p: Int, banned: IntArray, k: Int): IntArray {val ret = IntArray(n) {-1}
        // 初始位
        ret[p] = 0
        // 禁止位
        val bannedSet = banned.toHashSet()
        // BFS（最小跳转索引）val queue = LinkedList<Int>()
        queue.offer(p)
        while (!queue.isEmpty()) {val i = queue.poll()!!
            val min = Math.max(i - k + 1, k - i - 1)
            val max = Math.min(i + k - 1, 2 * n - k - i - 1)
            val curStep = ret[i] + 1
            for (j in min..max step 2) {
                // 不可达
                if (bannedSet.contains(j)) continue
                // 已拜访
                if (ret[j] != -1) continue
                // 可达
                ret[j] = curStep
                // 入队
                queue.offer(j)
            }
        }
        return ret
    }
}

复杂度剖析：

• 工夫复杂度：$O(n·k)$ 每个元素最多拜访 1 次，且每轮最多须要拜访 $k$ 个元素。
• 空间复杂度：$O(n)$ 队列的长度最大为 $n$。

题解二（BFS + 均衡二叉树）

在题解一中，当 k 比拟大时每轮 BFS 中会反复判断曾经被标记过的地位，如何防止呢？咱们能够提前将所有下标退出到散列表中，在每次标记后将下标从散列表移除，这样能防止反复拜访曾经标记过的地位。

其次，因为每轮中须要标记的区间位于 [min, max]，那么咱们能够将散列表降级为基于均衡二叉树的 TreeSet，以便在 O(lgn) 工夫内找到区间中的元素。具体形式是寻找树中大于等于 min 的最小元素（且小于等于 max），将其标记和移除。

最初，因为偶数下标和奇数下标是离开的，所以须要建设两个均衡二叉树。

class Solution {fun minReverseOperations(n: Int, p: Int, banned: IntArray, k: Int): IntArray {val ret = IntArray(n) {-1}
        // 初始位
        ret[p] = 0
        // 禁止位
        val bannedSet = banned.toHashSet()
        // 均衡二叉树
        val sets = Array(2) {TreeSet<Int>() }
        for (i in 0 until n) {if (i != p && !bannedSet.contains(i)) sets[i % 2].add(i)
        }
        // BFS（最小跳转索引）val queue = LinkedList<Int>()
        queue.offer(p)
        while (!queue.isEmpty()) {val i = queue.poll()!!
            val min = Math.max(i - k + 1, k - i - 1)
            val max = Math.min(i + k - 1, 2 * n - k - i - 1)
            val curStep = ret[i] + 1
            // 依据左端点确定奇偶性（右端点也行）val set = sets[min % 2]
            // 枚举均衡树中的 [min,max] 区间
            while (true) {val index = set.ceiling(min) ?: break // 大于等于 min 的最小键值
                if (index > max) break
                // 标记并删除
                set.remove(index)
                ret[index] = curStep
                // 入队
                queue.offer(index)
            }
        }
        return ret
    }
}

复杂度剖析：

• 工夫复杂度：$O(nlgn + nlgn)$ 建均衡树为 $O(nlgn)$，BFS 中每个元素最多删除一次，每轮须要 $O(lgn)$ 工夫找到左边界，整体是 $O(nlgn)$；
• 空间复杂度：$O(n)$ 均衡二叉树空间。

<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 点击上方按钮关注 </span>
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 每周继续原创更新 </span>
<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:16px;”> 与你一起深度思考 </span>

<span style=”display:block;text-align:center;color:black;font-weight:bold;font-size:18px;”>The End</span>

<span style=”display:block;text-align:center;color:black;font-size:12px;”>—— 我 们 下 次 见 ——</span>