本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 <彭旭锐> 提问。
大家好，我是小彭。
今天是 LeetCode 第 334 场周赛，你参加了吗？这场周赛考察范围比较基础，整体难度比较平均，第一题难度偏高，第四题需要我们在算法里实现 “反复横跳”，非常有意思。
小彭的 Android 交流群 02 群来了，公众号回复 “加群” 加入我们~
https://leetcode.cn/problems/left-and-right-sum-differences/
给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：
其中：
返回数组 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 result = Math.abs(preSum - sufSum) preSum += nums } return result }} 复杂度分析：
https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/
给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
返回 word 的可整除数组。
这道题主要靠大数处理。
将前缀字符串 <0, i> 转换为有 2 种方式：
但是，这 2 种方式在大数 case 中会遇到整型溢出变为负数，导致判断出错的情况，我们想办法保证加法运算不会整型溢出。我们发现： 在处理完 位置后，不必记录 <0, i-1> 的整段前缀，而仅需要记录前缀对 m 的取模结果。
例如当 m 为 3 时，“11 * 10 + 1 = 111” 与 “(11 % 3) * 10 + 1 = 21” 都能够对 3 整除。也可以这样理解：前缀中能被 m 整除的加法因子在后续运算中乘以 10 后依然能够被 m 整数，所以这部分加法因子应该尽早消掉。
另外还有一个细节：由于 m 的最大值是 109，前缀的取模结果的最大值为 109−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 - '0') num %= m if (num == 0L) div = 1 } return div }} 复杂度分析：
https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/
给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
这道题的难度是找到贪心规律。
题目要求：选择两个互不相同且未标记的下标 i 和 j ，满足 2 * nums <= nums
比赛过程中的思考过程记录下来：
陷入僵局……
开始转换思路：能否将数组拆分为两部分，作为 nums 的分为一组，作为 nums
设数组的长度为 n，最大匹配对数为 k。
将数组拆分为两部分后：
可以使用双指针求解：
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 * 2 <= nums) { 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 <= nums) i++ } return i * 2 }} 复杂度分析：
https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/
给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid
你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。
请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。
这道题是单源正权最短路的衍生问题，先回顾以一下类似的最短路问题解决方案：
这道题是求从一个源点到目标点的最短路径，并且这条路径上没有负权值，符合 Dijkstra 算法的应用场景。
Dijkstra 算法的本质是贪心 + BFS，我们需要将所有节点分为 2 类，在每一轮迭代中，我们从 “候选集” 中选择距离起点最短路长度最小的节点，由于该点不存在更优解，所以可以用该点来 “松弛” 相邻节点。
现在，我们分析在题目约束下，如何将原问题转换为 Dijkstra 最短路问题。
我们定义 dis
现在需要思考如何推导出递推关系：
假设已经确定到达位置 (i, j) 的最短时间是 time，那么相邻位置 (x, y) 的最短时间为：
至此，我们可以写出朴素版本的算法。
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 && (-1 == x || dis < dis)) { x = i y = j } } } val time = dis // 终止条件 if (x == n - 1 && y == m - 1) return time // 标记 visit = 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) continue var newTime = Math.max(time + 1, grid) newTime += (newTime - newX - newY) % 2 // 松弛相邻点 if (newTime < dis) { dis = newTime } } } }} 复杂度分析：
朴素 Dijkstra 的每轮迭代中需要遍历 N 个节点寻找候选集中的最短路长度。
事实上，这 N 个节点中有部分是 “确定集”，有部分是远离起点的边缘节点，每一轮都遍历所有节点显得没有必要。常用的套路是配合小顶堆记录候选集，以均摊 �(���) 时间找到深度最近的节点中的最短路长度：
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) newTime += (newTime - newX - newY) % 2 // 松弛相邻点 if (newTime < dis) { dis = newTime heap.offer(intArrayOf(newX, newY, newTime)) } } } }} 复杂度分析：
这道题也有二分的做法。
为了能够有充足的时间走到目标点，我们可以考虑在起点进行反复横跳消耗时间 0/2/4/6/8/12 … MAX_VALUE。极端情况下，只要我们在起点消耗足够长的时间后，总能够有充足的时间走到右下角。
我们发现在起点消耗时间对结果的影响具有单调性：
因此我们的算法是：使用二分查找寻找满足条件的最小 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, 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 = 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) continue // 不可访问 if (time < grid) continue // 可访问 if (newX == 0 && newY == 0) return true queue.offer(intArrayOf(newX, newY)) visit = true } } // 时间流逝 1 个单位 time-- } return false }} 复杂度分析：
这周的周赛题目就讲到这里，我们下周见。
