LeetCode 周赛 340，质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树
本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，我是小彭。
上周跟大家讲到小彭文章风格的问题，和一些朋友聊过以后，至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小，但却有很多像我一样的初学者，他们有兴趣参加但容易被题目难度和大神选手的题解劝退。
考虑到这些跟我一样的小白，我决定算法题解风格会向这些初学者倾斜，我们不会强调最优解法，而是强调从题意分析到问题抽象，再从暴力解法一步步升级到最优解法的推导过程，希望能帮到喜欢算法的朋友，向 Guardian 出发。
好一波强行自证价值？ ??
今天讲 LeetCode 单周赛第 340 场，今天状态不好，掉了一波大分。
2614. 对角线上的质数（Easy）
这道题是最近第 2 次出现质数问题，注意 1 不是质数！
- 质数判断：$O(n·\sqrt(U))$
2615. 等值距离和（Medium）
这道题是标准的前缀和数组题目，我们有从暴力到前缀和的解法，最后有消除前缀和数组的最优解法，理解从暴力解法到最优解法的推导过程非常重要。
- 题解 1：暴力 $O(n^2)$
- 题解 2：前缀和数组 $O(n) + O(n)$
- 题解 3：前缀和 + DP $O(n) + O(1)$
2616. 最小化数对的最大差值（Medium）
这道题是 “极大化最小值” 问题，与以前我们讲过的 “高楼丢鸡蛋” 问题属于同一种类型，理解 “极大化最小值” 中的单调性与二分查找的思路非常重要。
- 贪心 + 二分查找 $O(nlgn + nlgU)$
2617. 网格图中最少访问的格子数（Hard）
这道题是经典题目 45. 跳跃游戏 II 的二维版本，我创新性地从图的最短路视角理解 跳跃游戏 II，再迁移到这道二维数组问题上，难度降低为 Medium。
- 最短路 BFS + 平衡二叉树 + 队列 $O(nm·(lgn + lgm))$
2614. 对角线上的质数（Easy）
题目地址
https://leetcode.cn/problems/prime-in-diagonal
题目描述
给你一个下标从 0 开始的二维整数数组 nums 。
返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。
注意：
- 如果某个整数大于
1，且不存在除1和自身之外的正整数因子，则认为该整数是一个质数。 - 如果存在整数
i，使得nums[i][i] = val或者nums[i][nums.length - i - 1]= val，则认为整数val位于nums的一条对角线上。
题解（质数）
遍历两条对角线上的元素，如果是质数则更新答案。注意 1 不是质数！
另外再检查数据量，数组的长度 n 最大为 300，而数据最大值为 4*10^6，所以用朴素的质数判断算法能满足要求。
class Solution {
fun diagonalPrime(nums: Array<IntArray>): Int {
var ret = 0
val n = nums.size
for (i in 0 until n) {
val num1 = nums[i][i]
val num2 = nums[i][n - 1 - i]
if (num1 > ret && isPrime(num1)) ret = num1
if (num2 > ret && isPrime(num2)) ret = num2
}
return ret
}
private fun isPrime(num: Int): Boolean {
if (num == 1) return false
var x = 2
while (x * x <= num) {
if (num % x == 0) {
return false
}
x++
}
return true
}
}
复杂度分析：
- 时间复杂度：$O(n·\sqrt(U))$ 其中 n 是 nums 二维数组的长度，U 是输入数据的最大值；
- 空间复杂度：$O(1)$ 仅使用常量级别空间。
近期周赛质数问题：
2615. 等值距离和（Medium）
题目地址
https://leetcode.cn/problems/sum-of-distances/
题目描述
给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。
返回数组 **arr 。
问题分析
容易想到，不同数值之间互不影响，所以先对数组元素分组，再依次计算组内元素之间的距离差绝对值之和。
题解一（暴力 · 超出时间限制）
暴力解法是计算每个位置与其他组内元素的距离差绝对值。
class Solution {
fun distance(nums: IntArray): LongArray {
val n = nums.size
// 分组
val map = HashMap<Int, ArrayList<Int>>()
for (index in nums.indices) {
map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
}
val ret = LongArray(n)
// 暴力
for ((_, indexs) in map) {
for (i in indexs.indices) {
for (j in indexs.indices) {
ret[indexs[i]] += 0L + Math.abs(indexs[i] - indexs[j])
}
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：$O(n^2)$ 其中 n 为 nums 数组的长度
- 空间复杂度：$O(1)$ 不考虑分组的数据空间。
题解二（前缀和数组）
分析计算元素 x 与组内元素距离差绝对值之和的过程：
以组内下标为 [0, 1, 2, 3, 4, 5] 为例，下标 [2] 位置的距离和计算过程为：
- (x - 0) + (x - 1) + (x - x) + (3 - x) + (4 - x) + (5 - x)
我们以 [2] 为分割点将数组分为两部分，则发现：
- (x - 0) - (x - 1) 正好等于 (左边元素个数 * x) - 左边元素之和
- (3 - x) + (4 - x) + (5 - x) 正好等于 (右边元素之和) - (右边元素个数 * x)
数组区间和有前缀和的套路做法，可以以空间换时间降低时间复杂度。
- 细节：x * i 是 Int 运算会溢出，需要乘以 1 转换为 Long 运算
class Solution {
fun distance(nums: IntArray): LongArray {
val n = nums.size
// 分组
val map = HashMap<Int, ArrayList<Int>>()
for (index in nums.indices) {
map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
}
val ret = LongArray(n)
// 分组计算
for ((_, indexs) in map) {
val m = indexs.size
// 前缀和
val preSums = LongArray(m + 1)
for (i in indexs.indices) {
preSums[i + 1] = preSums[i] + indexs[i]
}
for ((i, x) in indexs.withIndex()) {
// x * i 是 Int 运算会溢出，需要乘以 1 转换为 Long 运算
val left = 1L * x * i - preSums[i]
val right = (preSums[m] - preSums[i + 1]) - 1L * x * (m - 1 - i)
ret[x] = left + right
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：$O(n)$ 其中 n 为 nums 数组的长度，分组、前缀和的时间是 $O(n)$，每个位置的距离和计算时间为 $O(1)$；
- 空间复杂度：$O(n)$ 不考虑分组空间，需要前缀和数组 $O(n)$。
题解三（前缀和 + DP）
将 left + right 的计算公式合并，则有
ret[x] = x * i - preSums[i] + (preSums[m] - preSums[i + 1]) - x * (m - 1 - i)
化简得：
ret[x] = (preSums[m] - preSums[i + 1]) - preSums[i] + x (2 * i - m + 1)
发现可以直接维护元素左右两边的元素之和，省去前缀和数据空间。
class Solution {
fun distance(nums: IntArray): LongArray {
val n = nums.size
// 分组
val map = HashMap<Int, ArrayList<Int>>()
for (index in nums.indices) {
map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
}
val ret = LongArray(n)
// 前缀和 DP
for ((_, indexs) in map) {
val m = indexs.size
var leftSum = 0L
var rightSum = 0L
for (element in indexs) {
rightSum += element
}
for ((i, x) in indexs.withIndex()) {
rightSum -= x
ret[x] = rightSum - leftSum + 1L * x * (2 * i - m + 1)
leftSum += x
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：$O(n)$ 其中 n 为 nums 数组的长度，分组时间是 $O(n)$，每个位置的距离和计算时间为 $O(1)$；
- 空间复杂度：$O(1)$ 不考虑分组空间。
相似题目：
2616. 最小化数对的最大差值（Medium）
题目地址
https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
问题分析
二分思路：“极大化最小值” 和 “极小化最小值” 存在单调性，是典型的二分查找问题。
- 二分的值越大，越能 / 越不能满足条件；
- 二分的值越小，越不能 / 越能满足条件。
贪心思路：由于元素位置不影响结果，可以先排序，尽量选相邻元素。
题解（二分 + 贪心）
如何二分？
- 二分的 left：0，无法构造出更小的差值；
- 二分的 right：数组的最大值 - 数组的最小值，无法构造出更大的差值；
- 我们可以选择一个差值 max，再检查差值 max 是否能够构造出来：
- 如果存在差值为 max 的方案：那么小于 max 的差值都不能构造（无法构造出更小的差值）；
- 如果不存在差值为 max 的方案：那么大于 max 的差值都能构造（任意调整数对使得差值变大即可）；
如何判断 “差值为 max 的方案”，即 “存在至少 p 个数对，它们的最大差值为 max 的方案” 存在？
这里需要思维转换，由于我们希望差值尽可能小，所谓我们不需要真的去构造差值为 max 的方案，而是尽可能构造出差值不超过 max 的方案，只要差值不超过 max 的方案数大于等于 p 个，那么至少有不高于 max 的差值方案存在。
举个例子，在数列 [1, 1, 2, 3, 7, 10] 中，p = 2，检查的差值 max = 5。此时我们构造数列对 {1, 1} {2, 3} 满足差值不超过 max 且方案数大于等于 p 个，那么 max 就是可构造的，且存在比 max 更优的方案。
所以，现在的问题转换为如何构造出尽可能多的数列数，使得它们的差值不超过 max？
如果当前元素 x 参与配对，那么配对相邻数的差值是最小的，否则 x 与不相邻数匹配无法得到更优解。
class Solution {
fun minimizeMax(nums: IntArray, p: Int): Int {
if (p == 0) return 0
// 排序
nums.sort()
val n = nums.size
// 二分查找
var left = 0
var right = nums[n - 1] - nums[0]
while (left < right) {
val mid = (left + right) ushr 1
if (check(nums, p, mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
// 检查
private fun check(nums: IntArray, p: Int, max: Int): Boolean {
var cnt = 0
var i = 0
while (i < nums.size - 1) {
if (nums[i + 1] - nums[i] <= max) {
// 选
i += 2
cnt += 1
} else {
i += 1
}
if (cnt == p) return true
}
return false
}
}
复杂度分析：
- 时间复杂度：$O(nlgn + nlgU)$ 其中 n 是 nums 数组的长度，U 是数组的最大差值。预排序时间为 $O(nlgn)$，二分次数为 $lgU$，每轮检查时间为 $O(n)$；
- 空间复杂度：$O(lgn)$ 排序递归栈空间。
2617. 网格图中最少访问的格子数（Hard）
题目地址
https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/
题目描述
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。
当你在格子 (i, j) 的时候，你可以移动到以下格子之一：
- 满足
j < k <= grid[i][j] + j的格子(i, k)（向右移动），或者 - 满足
i < k <= grid[i][j] + i的格子(k, j)（向下移动）。
请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。
问题分析
分析 1 - 题意：这道题的题意可能有点小绕，其实就是说站在 [i][j] 位置上，且 grid[i][j] = x，则最远可以走到向右 [i][j + x] 或向下 [i + x][j] 的位置上。现在求从左上角到右下角的最少移动次数，显然，这是一个在二维空间上的最短路问题，将格子之间的可达关系视为图的边，也可以视为图上的最短路问题。
初看之下这道题与经典题 45. 跳跃游戏 II 非常相似，简直是二维上的跳跃游戏问题。在 45. 这道题中，有时间复杂度 O(n) 且空间复杂度 O(1) 的动态规划解法，我也可以用图的思路去思考 45. 题（当然它的复杂度不会由于动态规划）
45. 跳跃游戏 II（最短路思路）
定义 dst[i] 表示到达 i 位置的最少跳跃次数，那么对于 i 位置可以到达的区间 (i+1, i + nums[i])，它们的最少跳跃次数最多不会高于 dst[i] + 1。
参考 Dijkstra 最短路算法的思路，我们将数组分为 “已确定集合” 和 “候选集合” 两组，那么对于已确定集合中最短路长度最小的节点 j，由于该点不存在更优解，所以可以用该点来确定其它店的最短路长度。
而且由于这道题中图的边权是 1，所以只要越早进入 “已确定集合” 中的点的最短路长度越低，不需要使用小顶堆来搜索 “已确定集合中最短路长度最小的节点”
class Solution {
fun jump(nums: IntArray): Int {
val n = nums.size
val INF = Integer.MAX_VALUE
// 候选集
val unVisitSet = HashSet<Int>(n).apply {
// 排除 0
for (i in 1 until n) {
this.add(i)
}
}
// 最短路长度
val dst = IntArray(n) { INF }
dst[0] = 0
// 队列
val queue = LinkedList<Int>()
queue.offer(0)
while (!queue.isEmpty()) {
// 由于边权为 1，队列中最先访问的节点一定是最短路长度最短的节点
val from = queue.poll()
// 更新可达范围
for (to in from + 1..Math.min(from + nums[from], n - 1)) {
if (!unVisitSet.contains(to)) continue
// 最短路
queue.offer(to)
dst[to] = dst[from] + 1
// 从候选集移除
unVisitSet.remove(to)
// 到达终点
if (to == n - 1) break
}
}
return dst[n - 1]
}
}
复杂度分析：
- 时间复杂度：$O(n^2)$ 其中 n 是 nums 数组的长度，每个节点最多入队一次，每次出队最多需要扫描 n - 1 个节点
- 空间复杂度：$O(n)$
在内层循环更新可达范围时，会重复检查已经确定最短路长度的点，我们可以使用平衡二叉树优化，这就类似于上一场周赛中第 4 题 2612. 最少翻转操作数 的思路。
class Solution {
fun jump(nums: IntArray): Int {
val n = nums.size
val INF = Integer.MAX_VALUE
// 候选集（平衡二叉树）
val unVisitSet = TreeSet<Int>().apply {
// 排除 0
for (i in 1 until n) {
this.add(i)
}
}
// 最短路长度
val dst = IntArray(n) { INF }
dst[0] = 0
// 队列
val queue = LinkedList<Int>()
queue.offer(0)
while (!queue.isEmpty()) {
// 由于边权为 1，队列中最先访问的节点一定是最短路长度最短的节点
val from = queue.poll()
// 更新可达范围
val max = Math.min(from + nums[from], n - 1)
while (true) {
// 大于等于 from 的第一个元素
val to = unVisitSet.ceiling(from) ?: break
if (to > max) break
// 最短路
queue.offer(to)
dst[to] = dst[from] + 1
// 从候选集移除
unVisitSet.remove(to)
// 到达终点
if (to == n - 1) break
}
}
return dst[n - 1]
}
}
复杂度分析：
- 时间复杂度：$O(nlgn)$ 其中 n 是 nums 数组的长度，每个节点最多入队一次，每次寻找左边界的时间是 O(lgn);
- 空间复杂度：$O(n)$ 平衡二叉树空间。
题解（BFS + 平衡二叉树 + 队列）
理解了用最短路思路解决一维数组上的跳跃游戏 II，很容易推广到二维数组上：
- 1、由于题目每个位置有向右和向下两个选项，所以我们需要建立 m + n 个平衡二叉树；
- 2、由于存在向右和向下两种可能性
class Solution {
fun minimumVisitedCells(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
if (n == 1 && m == 1) return 1
// 每一列的平衡二叉树
val rowSets = Array(n) { TreeSet<Int>() }
val columnSets = Array(m) { TreeSet<Int>() }
for (row in 0 until n) {
for (column in 0 until m) {
if (row + column == 0) continue
rowSets[row].add(column)
columnSets[column].add(row)
}
}
// 队列（行、列、最短路长度）
val queue = LinkedList<IntArray>()
queue.offer(intArrayOf(0, 0, 1))
while (!queue.isEmpty()) {
val node = queue.poll()
val row = node[0]
val column = node[1]
val dst = node[2]
val step = grid[row][column]
// 向右
var max = Math.min(column + step, m - 1)
while (true) {
val to = rowSets[row].ceiling(column) ?: break
if (to > max) break
// 最短路
queue.offer(intArrayOf(row, to, dst + 1))
// 从候选集移除（行列都需要移除）
rowSets[row].remove(to)
columnSets[column].remove(row)
// 到达终点
if (row == n - 1 && to == m - 1) return dst + 1
}
// 向下
max = Math.min(row + step, n - 1)
while (true) {
val to = columnSets[column].ceiling(row) ?: break
if (to > max) break
// 最短路
queue.offer(intArrayOf(to, column, dst + 1))
// 从候选集移除（行列都需要移除）
rowSets[row].remove(row)
columnSets[column].remove(to)
// 到达终点
if (to == n - 1 && column == m - 1) return dst + 1
}
}
return -1
}
}
复杂度分析：
- 时间复杂度：$O(nm·(lgn + lgm))$ 其中 n 是行数，m 是列数，每个点最多入队一次，每次出队需要 O(lgn + lgm) 时间确定左边界；
- 空间复杂度：$O(nm)$ 平衡二叉树空间。
近期周赛最短路问题：
为了 Guardian 加油！