本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
今天是 LeetCode 第 334 场周赛，你参加了吗？这场周赛考察范围比较基础，整体难度比较平均，第一题难度偏高，第四题需要我们在算法里实现 “反复横跳”，非常有意思。
小彭的 Android 交流群 02 群来了，公众号回复 “加群” 加入我们~
2574. 左右元素和的差值（Easy）
题目地址
https://leetcode.cn/problems/left-and-right-sum-differences/
题目描述
给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：
answer.length == nums.lengthanswer[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)$ 最短路数组的空间。
这周的周赛题目就讲到这里，我们下周见。