技術文章 » 刷爆 LeetCode 周賽 339，貪心 / 排序 / 拓撲排序 / 平衡二元樹

刷爆 LeetCode 周賽 339，貪心 / 排序 / 拓撲排序 / 平衡二元樹

2023-04-03 21:00:46

本文已收錄到 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-substring-of-a-binary-string/

題目描述

給你一個僅由 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-with-conditions/

題目描述

給你一個整數陣列 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)$ 平衡二元樹空間。

點選上方按鈕關注
每週持續原創更新
與你一起深度思考



The End

—— 我 們 下 次 見 ——