LeetCode 周賽 334，在演演算法的世界裡反覆橫跳

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

大家好，我是小彭。

今天是 LeetCode 第 334 場周賽，你參加了嗎？這場周賽考察範圍比較基礎，整體難度比較平均，第一題難度偏高，第四題需要我們在演演算法裡實現 「反覆橫跳」，非常有意思。

---

小彭的 Android 交流群 02 群來了，公眾號回覆 「加群」 加入我們~

---

---

2574. 左右元素和的差值（Easy）

題目地址

https://leetcode.cn/problems/left-and-right-sum-differences/

題目描述

給你一個下標從 0 開始的整數陣列 nums ，請你找出一個下標從 0 開始的整數陣列 answer ，其中：

• answer.length == nums.length
• answer[i] = |leftSum[i] - rightSum[i]|

其中：

• leftSum[i] 是陣列 nums 中下標 i 左側元素之和。如果不存在對應的元素，leftSum[i] = 0 。
• rightSum[i] 是陣列 nums 中下標 i 右側元素之和。如果不存在對應的元素，rightSum[i] = 0 。

返回陣列 answer 。

題解

簡單模擬題，使用兩個變數記錄前字尾和。

class Solution {
    fun leftRigthDifference(nums: IntArray): IntArray {
        var preSum = 0
        var sufSum = nums.sum()
        val n = nums.size
        val result = IntArray(n)
        for (index in nums.indices) {
            sufSum -= nums[index]
            result[index] = Math.abs(preSum - sufSum)
            preSum += nums[index]
        }
        return result
    }
}

複雜度分析：

• 時間複雜度：$O(n)$。
• 空間複雜度：$O(1)$，不考慮結果陣列。

---

2575. 找出字串的可整除陣列（Medium）

題目地址

https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/

題目描述

給你一個下標從 0 開始的字串 word ，長度為 n ，由從 0 到 9 的數位組成。另給你一個正整數 m 。

word 的 可整除陣列 div  是一個長度為 n 的整數陣列，並滿足：

• 如果 word[0,...,i] 所表示的 數值 能被 m 整除，div[i] = 1
• 否則，div[i] = 0

返回 word 的可整除陣列。

題解

這道題主要靠大數處理。

將字首字串 [0, i] 轉換為有 2 種方式：

• 1、使用 String#substring(0, i + 1) 裁剪子串，再轉換為數位；
• 2、使用 字首 * 10 + word[i] 逐位計算。

但是，這 2 種方式在大數 case 中會遇到整型溢位變為負數，導致判斷出錯的情況，我們想辦法保證加法運算不會整型溢位。我們發現： 在處理完 [i - 1] 位置後，不必記錄 [0, i-1] 的整段字首，而僅需要記錄字首對 m 的取模結果。

例如當 m 為 3 時，「11 * 10 + 1 = 111」 與 「(11 % 3) * 10 + 1 = 21」 都能夠對 3 整除。也可以這樣理解：字首中能被 m 整除的加法因子在後續運算中乘以 10 後依然能夠被 m 整數，所以這部分加法因子應該儘早消掉。

另外還有一個細節：由於 m 的最大值是 $10^9$，字首的取模結果的最大值為 $10^9 - 1$，而當前位置的最大值是 9，加法後依然會溢位，因此我們要用 Long 記錄當前位置。

class Solution {
    fun divisibilityArray(word: String, m: Int): IntArray {
        val n = word.length
        val div = IntArray(n)
        var num = 0L
        for (index in word.indices) {
            num = num * 10 + (word[index] - '0')
            num %= m
            if (num == 0L) div[index] = 1
        }
        return div
    }
}

複雜度分析：

• 時間複雜度：$O(n)$。
• 空間複雜度：$O(1)$，不考慮結果陣列。

---

2576. 求出最多標記下標（Medium）

題目地址

https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/

題目描述

給你一個下標從 0 開始的整數陣列 nums 。

一開始，所有下標都沒有被標記。你可以執行以下操作任意次：

• 選擇兩個 互不相同且未標記 的下標 i 和 j ，滿足 2 * nums[i] <= nums[j] ，標記下標 i 和 j 。

請你執行上述操作任意次，返回 nums 中最多可以標記的下標數目。

題解（排序 + 貪心 + 雙指標）

這道題的難度是找到貪心規律。

題目要求：選擇兩個互不相同且未標記的下標 i 和 j ，滿足 2 * nums[i] <= nums[j] ，標記下標 i 和 j 。我們發現題目並不關心 [i] 和 [j] 的選擇順序，所以對排序不會影響問題結果，而且排序能夠更方便地比較元素大小，因此題目的框架應該是往 排序 + [貪心 / 雙指標 / 二分 / DP] 的思路思考。

比賽過程中的思考過程記錄下來：

• 嘗試 1 - 排序 + 貪心雙指標：nums[i] 優先使用最小值，nums[j] 優先使用最大值，錯誤用例：[1 2 3 6]；
• 嘗試 2 - 排序 + 貪心：nums[i] 優先使用最小值，nums[j] 使用大於 nums[i] 的最小值，錯誤用例：[1 2 4 6]；
• 嘗試 3- 排序 + 貪心：從後往前遍歷，nums[i] 優先使用較大值，nums[j] 使用大於 nums[i] 的最小值，錯誤用例：[2 3 4 8]。

陷入僵局……

開始轉換思路：能否將陣列拆分為兩部分，作為 nums[i] 的分為一組，作為 nums[j] 的分為一組。 例如，在用例 [1 2 | 3 6] 和 [1 2 | 4 6] 和 [2 3 | 4 8]中，將陣列的前部分作為 nums[i] 而後半部分作為 nums[j] 時，可以得到最優解，至此發現貪心規律。

設陣列的長度為 n，最大匹配對數為 k。

• 貪心規律 1：從小到大排序後，使用陣列的左半部分作為 nums[i] 且使用陣列的右半部分作為 nums[j] 總能取到最優解。反之，如果使用右半部分的某個數 nums[t] 作為 nums[i]，相當於佔用了一個較大的數，不利於後續 nums[i] 尋找配對。

將陣列拆分為兩部分後：

• 貪心規律 2：從小到大排序後，當固定 nums[i] 時，nums[j] 越小越好，否則會佔用一個較大的位置，不利於後續 nums[i] 尋找配對。因此最優解一定是使用左半部分的最小值與右半部分的最小值配對。

可以使用雙指標求解：

class Solution {
    fun maxNumOfMarkedIndices(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        var count = 0
        var j = (n + 1) / 2
        outer@ for (i in 0 until n / 2) {
            while (j < n) {
                if (nums[i] * 2 <= nums[j++]) {
                    count += 2
                    continue@outer
                }
            }
        }
        return count
    }
}

簡化寫法：

class Solution {
    fun maxNumOfMarkedIndices(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        var i = 0
        for (j in (n + 1) / 2 until n) {
            if (2 * nums[i] <= nums[j]) i++
        }
        return i * 2
    }
}

複雜度分析：

• 時間複雜度：$O(nlgn + n)$ 其中 $n$ 為 $nums$ 陣列長度，排序時間 $O(nlgn)$，雙指標遍歷時間 $O(n)$；
• 空間複雜度：$O(lgn)$ 排序遞迴棧空間。

---

2577. 在網格圖中存取一個格子的最少時間（Hard）

題目地址

https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/

題目描述

給你一個 m x n 的矩陣 grid ，每個元素都為 非負 整數，其中 grid[row][col] 表示可以存取格子 (row, col) 的 最早 時間。也就是說當你存取格子 (row, col) 時，最少已經經過的時間為 grid[row][col] 。

你從 最左上角 出發，出發時刻為 0 ，你必須一直移動到上下左右相鄰四個格子中的 任意 一個格子（即不能停留在格子上）。每次移動都需要花費 1 單位時間。

請你返回 最早 到達右下角格子的時間，如果你無法到達右下角的格子，請你返回 -1 。

前置知識

這道題是單源正權最短路的衍生問題，先回顧以一下類似的最短路問題解決方案：

• Dijkstra 演演算法（單源正權最短路）：
  • 本質上是貪心 + BFS；
  • 負權邊會破壞貪心策略的選擇，無法處理含負權問題；
  • 稀疏圖小頂堆的寫法更優，稠密圖樸素寫法更優。
• Floyd 演演算法（多源匯正權最短路）
• Bellman Ford 演演算法（單源負權最短路）
• SPFA 演演算法（單源負權最短路）

這道題是求從一個源點到目標點的最短路徑，並且這條路徑上沒有負權值，符合 Dijkstra 演演算法的應用場景。

Dijkstra 演演算法的本質是貪心 + BFS，我們需要將所有節點分為 2 類，在每一輪迭代中，我們從 「候選集」 中選擇距離起點最短路長度最小的節點，由於該點不存在更優解，所以可以用該點來 「鬆弛」 相鄰節點。

• 1、確定集：已確定（從起點開始）到當前節點最短路徑的節點；
• 2、候選集：未確定（從起點開始）到當前節點最短路徑的節點。

現在，我們分析在題目約束下，如何將原問題轉換為 Dijkstra 最短路問題。

題解一（樸素 Dijkstra 演演算法）

我們定義 dis[i][j] 表示到達 (i, j) 的最短時間，根據題目約束 「grid[row][col]表示可以存取格子 (row, col) 最早時間」 可知，dis[i][j] 的最小值不會低於 grid[i][j]。

現在需要思考如何推匯出遞推關係：

假設已經確定到達位置 (i, j) 的最短時間是 time，那麼相鄰位置 (x, y) 的最短時間為：

• 如果 time + 1 ≥ grid[x][y]，那麼不需要等待就可以進入，進入 (x, y) 的最短時間就是 time + 1；
• 如果 time + 1 < grid[x][y]，那麼必須通過等待消耗時間進入。由於題目不允許原地停留消耗時間，因此只能使出回退 「反覆橫跳 A→ B → A」 來消耗時。因此有 dis[x][y] = Math.max(time + 1, grid[x][y])。
• 另外，根據網格圖的性質，到達 (x, y) 點的最短時間 dis[x][y] 與 x + y 的奇偶性一定相同，如果不同必然需要 + 1。例如 $\begin{bmatrix}
  0 & 1 \
  1 & 3
  \end{bmatrix}$的最短路徑是 3 + 1= 4，而 $\begin{bmatrix}
  0 & 1 \
  1 & 2
  \end{bmatrix}$的最短路徑是 2。

至此，我們可以寫出樸素版本的演演算法。

class Solution {
    fun minimumTime(grid: Array<IntArray>): Int {
        // 無解
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1
        // 無效值
        val INF = Integer.MAX_VALUE
        val n = grid.size
        val m = grid[0].size
        // 最短路長度
        val dis = Array(n) { IntArray(m) { INF } }.apply {
            this[0][0] = 0
        }
        // 存取標記
        val visit = Array(n) { BooleanArray(m) }
        // 方向
        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
        while (true) {
            var x = -1
            var y = -1
            // 尋找候選集中的最短時間
            for (i in 0 until n) {
                for (j in 0 until m) {
                    if (!visit[i][j] && (-1 == x || dis[i][j] < dis[x][y])) {
                        x = i
                        y = j
                    }
                }
            }
            val time = dis[x][y]
            // 終止條件
            if (x == n - 1 && y == m - 1) return time
            // 標記
            visit[x][y] = true
            // 列舉相鄰位置
            for (direction in directions) {
                val newX = x + direction[0]
                val newY = y + direction[1]
                // 越界
                if (newX !in 0 until n || newY !in 0 until m || visit[newX][newY]) continue
                var newTime = Math.max(time + 1, grid[newX][newY])
                newTime += (newTime - newX - newY) % 2
                // 鬆弛相鄰點
                if (newTime < dis[newX][newY]) {
                    dis[newX][newY] = newTime
                }
            }
        }
    }
}

複雜度分析：

• 時間複雜度：$O(N^2)$ 其中 $N$ 為網格的個數 $nm$，在這道題中會超時；
• 空間複雜度：$O(N^2)$ 最短路陣列的空間。

題解二（Dijkstra 演演算法 + 最小堆）

樸素 Dijkstra 的每輪迭代中需要遍歷 N 個節點尋找候選集中的最短路長度。

事實上，這 N 個節點中有部分是 「確定集」，有部分是遠離起點的邊緣節點，每一輪都遍歷所有節點顯得沒有必要。常用的套路是配合小頂堆記錄候選集，以均攤 $O(lgN)$ 時間找到深度最近的節點中的最短路長度：

class Solution {
    fun minimumTime(grid: Array<IntArray>): Int {
        // 無解
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1
        // 無效值
        val INF = Integer.MAX_VALUE
        val n = grid.size
        val m = grid[0].size
        // 最短路長度
        val dis = Array(n) { IntArray(m) { INF } }.apply {
            this[0][0] = 0
        }
        // 小頂堆：三元組 <x, y, dis>
        val heap = PriorityQueue<IntArray>() { e1, e2 ->
            e1[2] - e2[2]
        }.apply {
            this.offer(intArrayOf(0, 0, 0))
        }
        // 方向
        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
        while (true) {
            // 尋找候選集中的最短時間
            val node = heap.poll()
            val x = node[0]
            val y = node[1]
            val time = node[2]
            // 終止條件
            if (x == n - 1 && y == m - 1) return time
            // 列舉相鄰位置
            for (direction in directions) {
                val newX = x + direction[0]
                val newY = y + direction[1]
                // 越界
                if (newX !in 0 until n || newY !in 0 until m) continue
                var newTime = Math.max(time + 1, grid[newX][newY])
                newTime += (newTime - newX - newY) % 2
                // 鬆弛相鄰點
                if (newTime < dis[newX][newY]) {
                    dis[newX][newY] = newTime
                    heap.offer(intArrayOf(newX, newY, newTime))
                }
            }
        }
    }
}

複雜度分析：

• 時間複雜度：$O(NlgN)$ 每輪迭代最壞以 $O(lgN)$ 時間取堆頂；
• 空間複雜度：$O(N^2)$ 最短路陣列的空間。

題解三（二分 + BFS）

這道題也有二分的做法。

為了能夠有充足的時間走到目標點，我們可以考慮在起點進行反覆橫跳消耗時間 0/2/4/6/8/12 … MAX_VALUE。極端情況下，只要我們在起點消耗足夠長的時間後，總能夠有充足的時間走到右下角。

我們發現在起點消耗時間對結果的影響具有單調性：

• 如果 fullTime 可以到達目標點，那麼大於 fullTime 的所有時間都充足時間到達目標點；
• 如果 fullTime 不能到達目標點，那麼小於 fullTime 的所有時間都不足以到達目標點。

因此我們的演演算法是：使用二分查詢尋找滿足條件的最小 fullTime，並在每輪迭代中使用 BFS 走曼哈頓距離，判斷是否可以走到目標點，最後再修正 fullTime 與 m + n 的奇偶性。

class Solution {
    // 方向
    private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

    fun minimumTime(grid: Array<IntArray>): Int {
        // 無解
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1
        // 無效值
        val INF = Integer.MAX_VALUE
        val n = grid.size
        val m = grid[0].size
        var left = Math.max(grid[n - 1][m - 1], m + n - 2)
        var right = 1e5.toInt() + m + n - 2
        while (left < right) {
            val mid = (left + right) ushr 1
            if (checkBFS(grid, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        // (left - m + n) % 2 確保奇偶性一致
        return left + (left - m + n) % 2
    }

    // 檢查從 fullTime 開始是否可以等待能否到達左上角
    private fun checkBFS(grid: Array<IntArray>, fullTime: Int): Boolean {
        val n = grid.size
        val m = grid[0].size
        val visit = Array(n) { BooleanArray(m) }.apply {
            this[n - 1][m - 1] = true
        }
        val queue = LinkedList<IntArray>().apply {
            this.offer(intArrayOf(n - 1, m - 1))
        }
        var time = fullTime - 1
        while (!queue.isEmpty()) {
            // 層序遍歷
            for (count in 0 until queue.size) {
                val node = queue.poll()!!
                val x = node[0]
                val y = node[1]
                for (direction in directions) {
                    val newX = x + direction[0]
                    val newY = y + direction[1]
                    // 越界
                    if (newX !in 0 until n || newY !in 0 until m) continue
                    // 已存取
                    if (visit[newX][newY]) continue
                    // 不可存取
                    if (time < grid[newX][newY]) continue
                    // 可存取
                    if (newX == 0 && newY == 0) return true
                    queue.offer(intArrayOf(newX, newY))
                    visit[newX][newY] = true
                }
            }
            // 時間流逝 1 個單位
            time--
        }
        return false
    }
}

複雜度分析：

• 時間複雜度：$O(N·lgU)$ 其中 $N$ 為網格的個數 $nm$，$U$ 是資料的最大值；
• 空間複雜度：$O(N^2)$ 最短路陣列的空間。

---

這周的周賽題目就講到這裡，我們下週見。