大家好咆畏，我是小彭南捂。

上周末是 LeetCode 第 339 場周賽，你參加了嗎旧找？這場周賽覆蓋的知識點(diǎn)比較少溺健，前三題很簡單，第四題上難度钮蛛。

周賽大綱

2609. 最長平衡子字符串（Easy）

• 模擬：

2610. 轉(zhuǎn)換二維數(shù)組（Medium）

• 貪心：

2611. 老鼠和奶酪（Medium）

• 排序 + 貪心：

2612. 最少翻轉(zhuǎn)操作數(shù)（Hard）

• 題解一：拓?fù)渑判?· 超出時(shí)間限制
• 題解二：BFS + 平衡二叉樹

2609. 最長平衡子字符串（Easy）

題目地址

https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/

題目描述

給你一個(gè)僅由 0 和 1 組成的二進(jìn)制字符串 s 鞭缭。

如果子字符串中 所有的 0 都在 1 之前 且其中 0 的數(shù)量等于 1 的數(shù)量，則認(rèn)為 s 的這個(gè)子字符串是平衡子字符串魏颓。請注意岭辣，空子字符串也視作平衡子字符串。

返回 s 中最長的平衡子字符串長度甸饱。

子字符串是字符串中的一個(gè)連續(xù)字符序列沦童。

題解（模擬）

簡單模擬題。

維護(hù)連續(xù) 0 的計(jì)數(shù) cnt0 和連續(xù) 1 的計(jì)數(shù) cnt1叹话，并在 cnt0 == cnt1 時(shí)更新最長平衡子串長度為 2 * cnt1偷遗。另外，在每段 0 的起始位置重新計(jì)數(shù)渣刷。

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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： 其中 為 數(shù)組的長度鹦肿；
• 空間復(fù)雜度： 僅使用常數(shù)級別變量。

2610. 轉(zhuǎn)換二維數(shù)組（Medium）

題目地址

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

題目描述

給你一個(gè)整數(shù)數(shù)組 nums 辅柴。請你創(chuàng)建一個(gè)滿足以下條件的二維數(shù)組：

• 二維數(shù)組應(yīng)該 只 包含數(shù)組 nums 中的元素箩溃。
• 二維數(shù)組中的每一行都包含 不同 的整數(shù)。
• 二維數(shù)組的行數(shù)應(yīng)盡可能 少 碌嘀。

返回結(jié)果數(shù)組涣旨。如果存在多種答案，則返回其中任何一種股冗。

請注意霹陡，二維數(shù)組的每一行上可以存在不同數(shù)量的元素。

題解（貪心）

貪心思路：首先計(jì)算每個(gè)元素的出現(xiàn)次數(shù)，為了避免同一行的重復(fù)烹棉，將重復(fù)元素從上到下排列到不同行中攒霹。

優(yōu)化：可以在一次遍歷中完成，在出現(xiàn)更大出現(xiàn)次數(shù)時(shí)增加一行浆洗，在更新元素技術(shù) cnt 后插入到第 cnt - 1 行催束。

class Solution {
    fun findMatrix(nums: IntArray): List<List<Int>> {
        val cnts = IntArray(201)
        val ret = LinkedList<LinkedList<Int>>()
        var maxCnt = 0
        // 計(jì)數(shù)
        for (num in nums) {
            // 累加
            val curCnt = ++cnts[num]
            // 創(chuàng)建新行
            if (curCnt > maxCnt) {
                maxCnt = curCnt
                ret.add(LinkedList<Int>())
            }
            // 分布
            ret[curCnt - 1].add(num)
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： 其中 為 數(shù)組的長度，每個(gè)元素訪問一次伏社；
• 空間復(fù)雜度： 計(jì)數(shù)數(shù)組空間抠刺。

2611. 老鼠和奶酪（Medium）

題目地址

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

題目描述

有兩只老鼠和 n 塊不同類型的奶酪，每塊奶酪都只能被其中一只老鼠吃掉摘昌。

下標(biāo)為 i 處的奶酪被吃掉的得分為：

• 如果第一只老鼠吃掉速妖，則得分為 reward1[i] 。
• 如果第二只老鼠吃掉聪黎，則得分為 reward2[i] 排作。

給你一個(gè)正整數(shù)數(shù)組 reward1 诽嘉，一個(gè)正整數(shù)數(shù)組 reward2 枕稀，和一個(gè)非負(fù)整數(shù) k 辨萍。

請你返回第一只老鼠恰好吃掉 k 塊奶酪的情況下烘跺，最大 得分為多少湘纵。

題解（排序 + 貪心）

容易理解：為了使最終得分最大，應(yīng)該讓每只老鼠吃到盡可能大的奶酪滤淳。

由于兩只老鼠吃的奶酪是互斥關(guān)系梧喷，因此我們可以先假設(shè)所有奶酪被第一只老鼠食得，然后再挑選 n - k 個(gè)奶酪還給第二只老鼠脖咐。

那么铺敌，對于每個(gè)位置 i，將奶酪從第一只老鼠還給第二只老鼠存在差值 diff = reward2[i] - reward1[i]屁擅，表示得分的差值為 diff偿凭。差值為正得分變大，差值為負(fù)得分降低派歌，顯然降低越少越好弯囊。

因此，我們的算法是對 diff 排序胶果，將得分降低越大的位置保留給第一只老鼠匾嘱，其他還給第二只老鼠。

class Solution {
    fun miceAndCheese(reward1: IntArray, reward2: IntArray, k: Int): Int {
        // 貪心：優(yōu)先選擇差值最大的位置
        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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： 其中 為 數(shù)組的長度早抠；
• 空間復(fù)雜度： 索引數(shù)組和遞歸楒樱空間。

2612. 最少翻轉(zhuǎn)操作數(shù)（Hard）

題目地址

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

題目描述

給你一個(gè)整數(shù) n 和一個(gè)在范圍 [0, n - 1] 以內(nèi)的整數(shù) p ，它們表示一個(gè)長度為 n 且下標(biāo)從 0 開始的數(shù)組 arr 悬垃，數(shù)組中除了下標(biāo)為 p 處是 1 以外游昼，其他所有數(shù)都是 0 。

同時(shí)給你一個(gè)整數(shù)數(shù)組 banned 尝蠕，它包含數(shù)組中的一些位置酱床。banned 中第 i 個(gè)位置表示 arr[banned[i]] = 0 ，題目保證 banned[i] != p 趟佃。

你可以對 arr 進(jìn)行 若干次 操作扇谣。一次操作中，你選擇大小為 k 的一個(gè) 子數(shù)組 闲昭，并將它 翻轉(zhuǎn) 罐寨。在任何一次翻轉(zhuǎn)操作后，你都需要確保 arr 中唯一的 1 不會到達(dá)任何 banned 中的位置序矩。換句話說鸯绿，arr[banned[i]] 始終 保持 0 。

請你返回一個(gè)數(shù)組 ans 簸淀，對于 **[0, n - 1] 之間的任意下標(biāo) i 瓶蝴，ans[i] 是將 1 放到位置 i 處的 最少 翻轉(zhuǎn)操作次數(shù)，如果無法放到位置 i 處租幕，此數(shù)為 -1 舷手。

• 子數(shù)組 指的是一個(gè)數(shù)組里一段連續(xù) 非空 的元素序列。
• 對于所有的 i 劲绪，ans[i] 相互之間獨(dú)立計(jì)算男窟。
• 將一個(gè)數(shù)組中的元素 翻轉(zhuǎn) 指的是將數(shù)組中的值變成 相反順序 。

題解一（拓?fù)渑判?· 超出時(shí)間限制）

分析 1：對于翻轉(zhuǎn)窗口 [L, R] 中的位置 i贾富，翻轉(zhuǎn)后的下標(biāo)為

分析 2：首先位置 p 的翻轉(zhuǎn)次數(shù)恒等于 0歉眷，而 banned 數(shù)組表示的位置翻轉(zhuǎn)次數(shù)恒等于 -1。

分析 3：當(dāng)位置 i 位于翻轉(zhuǎn)窗口的左半部分時(shí)颤枪，將翻轉(zhuǎn)到更大位置汗捡；當(dāng)位置 i 位于翻轉(zhuǎn)窗口的右半部分時(shí)，將翻轉(zhuǎn)到更小位置畏纲；

分析 4：現(xiàn)在我們需要分析位置 i （初始 i 為 0 ）可以翻轉(zhuǎn)到的位置：

• 情況 1：如果將 i 作為翻轉(zhuǎn)窗口的左右邊界扇住，則有：
  • 位于左邊界時(shí)，翻轉(zhuǎn)后的下標(biāo)為 i + k - 1霍骄；
  • 位于有邊界時(shí)台囱，翻轉(zhuǎn)后的下標(biāo)為 i - k + 1。
• 情況 2：如果將 i 放在翻轉(zhuǎn)窗口內(nèi)部读整，則所有翻轉(zhuǎn)后的下標(biāo)正好構(gòu)成差值為 2 的等差數(shù)列簿训。

因此，i 可以翻轉(zhuǎn)的區(qū)間為 [i - k + 1, i + k - 1] 中間隔 2 的位置（排除 banned 數(shù)組），或者理解為奇偶性相同的下標(biāo)强品。

分析 5：由于翻轉(zhuǎn)窗口有位置限制膘侮，會限制翻轉(zhuǎn)：

• 窗口左邊界在位置 0 時(shí)，且 i 位于翻轉(zhuǎn)窗口的右半部分時(shí)（準(zhǔn)備向左翻）的榛，則翻轉(zhuǎn)后的位置是 0 + (k - 1) - i = k - 1 - i琼了。由于窗口無法繼續(xù)左移，所以小于 k - i - 1 的位置都不可達(dá)夫晌；
• 同理雕薪，窗口右邊界位于 n - 1 時(shí)，且 i 位于翻轉(zhuǎn)窗口的左邊部分時(shí)（準(zhǔn)備向右翻）晓淀，則翻轉(zhuǎn)后的位置是 (n - k) + (n - 1) - i = 2n - k - i - 1所袁。由于窗口無法繼續(xù)右移，所以大于 2n - k - i - 1 的位置都不可達(dá)凶掰。

綜上燥爷，可得翻轉(zhuǎn)后區(qū)間為 [max(i - k + 1, k - i - 1), min(i + k - 1, 2n - k - i - 1)] 中與 i 奇偶性相同的位置。

至此懦窘，容易發(fā)現(xiàn)問題可以用拓?fù)渑判颍˙FS 寫法）解決：初始時(shí)將 p 位置入隊(duì)前翎，隨后每一輪的翻轉(zhuǎn)次數(shù) + 1，并將該位置入隊(duì)畅涂。

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（最小跳轉(zhuǎn)索引）
        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) {
                // 不可達(dá)
                if (bannedSet.contains(j)) continue
                // 已訪問
                if (ret[j] != -1) continue
                // 可達(dá)
                ret[j] = curStep
                // 入隊(duì)
                queue.offer(j)
            }
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： 每個(gè)元素最多訪問 1 次港华，且每輪最多需要訪問 個(gè)元素。
• 空間復(fù)雜度： 隊(duì)列的長度最大為 毅戈。

題解二（BFS + 平衡二叉樹）

在題解一中苹丸，當(dāng) k 比較大時(shí)每輪 BFS 中會重復(fù)判斷已經(jīng)被標(biāo)記過的位置，如何避免呢苇经？我們可以提前將所有下標(biāo)加入到散列表中，在每次標(biāo)記后將下標(biāo)從散列表移除宦言，這樣能避免重復(fù)訪問已經(jīng)標(biāo)記過的位置扇单。

其次，由于每輪中需要標(biāo)記的區(qū)間位于 [min, max]奠旺，那么我們可以將散列表升級為基于平衡二叉樹的 TreeSet蜘澜，以便在 O(lgn) 時(shí)間內(nèi)找到區(qū)間中的元素。具體方式是尋找樹中大于等于 min 的最小元素（且小于等于 max）响疚，將其標(biāo)記和移除鄙信。

最后，由于偶數(shù)下標(biāo)和奇數(shù)下標(biāo)是分開的忿晕，所以需要建立兩個(gè)平衡二叉樹装诡。

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（最小跳轉(zhuǎn)索引）
        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
            // 根據(jù)左端點(diǎn)確定奇偶性（右端點(diǎn)也行）
            val set = sets[min % 2]
            // 枚舉平衡樹中的 [min,max] 區(qū)間
            while (true) {
                val index = set.ceiling(min) ?: break // 大于等于 min 的最小鍵值
                if (index > max) break
                // 標(biāo)記并刪除
                set.remove(index)
                ret[index] = curStep
                // 入隊(duì)
                queue.offer(index)
            }
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度： 建平衡樹為 ，BFS 中每個(gè)元素最多刪除一次，每輪需要 時(shí)間找到左邊界鸦采，整體是 宾巍；
• 空間復(fù)雜度： 平衡二叉樹空間。

<span style="display:block;text-align:center;color:black;font-weight:bold;font-size:16px;">點(diǎn)擊上方按鈕關(guān)注</span>
<span style="display:block;text-align:center;color:black;font-weight:bold;font-size:16px;">每周持續(xù)原創(chuàng)更新</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>