关于后端: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))$

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)$ 仅应用常量级别空间。

近期周赛质数问题：

2600. 质数减法运算（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)$。

将 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)$ 不思考分组空间。

类似题目：

1685. 有序数组中差绝对值之和

https://leetcode.cn/problems/minimize-the-maximum-difference-…

给你一个下标从 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)$ 排序递归栈空间。

https://leetcode.cn/problems/minimum-number-of-visited-cells-…

给你一个下标从 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 地位上，且 gridi = x，则最远能够走到向右 i 或向下 i + x 的地位上。当初求从左上角到右下角的起码挪动次数，显然，这是一个在二维空间上的最短路问题，将格子之间的可达关系视为图的边，也能够视为图上的最短路问题。

初看之下这道题与经典题 45. 跳跃游戏 II 十分类似，几乎是二维上的跳跃游戏问题。在 45. 这道题中，有工夫复杂度 O(n) 且空间复杂度 O(1) 的动静布局解法，我也能够用图的思路去思考 45. 题（当然它的复杂度不会因为动静布局）

定义 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)$ 均衡二叉树空间。

了解了用最短路思路解决一维数组上的跳跃游戏 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)$ 均衡二叉树空间。

近期周赛最短路问题：

2612. 起码翻转操作数（Hard）
2608. 图中的最短环（Hard）
2577. 在网格图中拜访一个格子的起码工夫（Hard）

为了 Guardian 加油！

关于后端:LeetCode-周赛-340质数-前缀和-极大化最小值-最短路-平衡二叉树

2614. 对角线上的质数（Easy）

题目地址

题目形容

题解（质数）

2615. 等值间隔和（Medium）

题目地址

题目形容

问题剖析

题解一（暴力 · 超出工夫限度）

题解二（前缀和数组）

题解三（前缀和 + DP）

2616. 最小化数对的最大差值（Medium）

题目地址

题目形容

问题剖析

题解（二分 + 贪婪）

2617. 网格图中起码拜访的格子数（Hard）

题目地址

题目形容

问题剖析

45. 跳跃游戏 II（最短路思路）

题解（BFS + 均衡二叉树 + 队列）