本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 发问。
大家好，欢迎来到小彭的 LeetCode 周赛解题陈述。
昨晚是 LeetCode 双周赛第 102 场，你参与了吗？这场比赛比较简略，拼的是板子手速，继上星期掉大分后算是回了一口血 。
2618. 查询网格图中每一列的宽度（Easy）
简略模仿题，无需解说。
- 模仿：O(nm)O(nm)
2619. 一个数组一切前缀的分数（Medium）
简略动态规划题，简略到像模仿题。
- 动态规划：O(n)O(n)
2620. 二叉树的堂兄弟节点 II（Medium）
考虑过程：递归→DFS→BFS。因为堂兄弟节点都在同一层，发现 “递归地削减问题规划求解原问题” 和 DFS 都不好编码，而 BFS 更符合 “层” 的概念。往 BFS 方向考虑后，简单找到解决方法。
- BFS：O(n)O(n)
2621. 规划能够求最短途径的图类（Hard）
最近周赛的最短路问题十分多，印象中现已连续呈现三次最短路问题。了解 Dijkstra 算法和 Floyd 算法的运用场景十分重要。
- 朴素 Dijkstra：O(m+q1⋅n2+q2)O(m + q_1n^2 + q_2)
- Dijkstra + 最小堆：O(m+q1⋅nlgm+q2)O(m + q_1nlgm+q_2)
- Floyd：O(m+n3+q1+q2⋅n2)O(m + n^3 + q_1 + q_2n^2)
2618. 查询网格图中每一列的宽度（Easy）
标题地址
leetcode.cn/problems/fi…
标题描绘
给你一个下标从0开端的m x n整数矩阵grid。矩阵中某一列的宽度是这一列数字的最大字符串长度。
- 比方说，假如
grid = [[-10], [3], [12]]，那么仅有一列的宽度是3，因为10的字符串长度为3。
请你回来一个巨细为n的整数数组ans，其间ans[i]是第i列的宽度。
一个有len个数位的整数x，假如是非负数，那么字符串长度为len，否则为len + 1。
题解（模仿）
class Solution {
fun findColumnWidth(grid: Array<IntArray>): IntArray {
val m = grid.size
val n = grid[0].size
val ret = IntArray(n)
for (column in 0 until n) {
for (row in 0 until m) {
ret[column] = Math.max(ret[column], "${grid[row][column]}".length)
}
}
return ret
}
}
复杂度剖析：
- 时刻复杂度：O(nm)O(nm) 其间 nn 和 mm 为 grid 数组的队伍巨细，每个节点最多拜访 1 次；
- 空间复杂度：O(1)O(1) 不考虑成果数组。
2619. 一个数组一切前缀的分数（Medium）
标题地址
leetcode.cn/problems/fi…
标题描绘
界说一个数组arr的转换数组conver为：
-
conver[i] = arr[i] + max(arr[0..i])，其间max(arr[0..i])是满足0 <= j <= i的一切arr[j]中的最大值。
界说一个数组arr的分数为arr转换数组中一切元素的和。
给你一个下标从0开端长度为n的整数数组nums，请你回来一个长度为n的数组**ans，其间ans[i]是前缀nums[0..i]的分数。
题解（动态规划）
简略动态规划题，简单发现递归联系：
- conver[i] = max{maxNum, arr[i]}
- dp[i] = dp[i-1] + conver[i]
class Solution {
fun findPrefixScore(nums: IntArray): LongArray {
val n = nums.size
val ret = LongArray(n)
// 初始状况
ret[0] = 2L * nums[0]
var maxNum = nums[0]
// DP
for (i in 1 until n) {
maxNum = Math.max(maxNum, nums[i])
ret[i] = ret[i - 1] + (0L + nums[i] + maxNum)
}
return ret
}
}
复杂度剖析：
- 时刻复杂度：O(n)O(n) 其间 nn 为 arrarr 数组的长度，每个节点最多拜访 1 次；
- 空间复杂度：O(1)O(1) 不考虑成果数组。
2620. 二叉树的堂兄弟节点 II（Medium）
标题地址
leetcode.cn/problems/co…
标题描绘
给你一棵二叉树的根root，请你将每个节点的值替换成该节点的一切堂兄弟节点值的和。
假如两个节点在树中有相同的深度且它们的父节点不同，那么它们互为堂兄弟。
请你回来修改值之后，树的根**root**。
注意，一个节点的深度指的是从树根节点到这个节点通过的边数。
题解（BFS）
剖析 1 – 递归：尝试分化左右子树求解问题，发现左右子树不独立，不再考虑此思路；
剖析 2 – DFS / BFS：因为堂兄弟节点都在同一层，而 BFS 更符合 “层” 的概念，往 BFS 方向考虑后，简单找到解决方法：在处理每一层的节点时，第一轮遍历先累计下一层节点的和，在第二轮遍历时更新下一层节点（取出自己和兄弟节点的值）。
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun replaceValueInTree(root: TreeNode?): TreeNode? {
if (null == root) return root
// BFS
val queue = LinkedList<TreeNode>()
queue.offer(root)
root.`val` = 0
while (!queue.isEmpty()) {
val size = queue.size
// 核算下一层的和
var nextLevelSum = 0
for (i in 0 until size) {
val node = queue[i]
if (null != node.left) nextLevelSum += node.left.`val`
if (null != node.right) nextLevelSum += node.right.`val`
}
for (count in 0 until size) {
val node = queue.poll()
// 减去非堂兄弟节点
var nextLevelSumWithoutNode = nextLevelSum
if (null != node.left) nextLevelSumWithoutNode -= node.left.`val`
if (null != node.right) nextLevelSumWithoutNode -= node.right.`val`
// 入队
if (null != node.left) {
queue.offer(node.left)
node.left.`val` = nextLevelSumWithoutNode
}
if (null != node.right) {
queue.offer(node.right)
node.right.`val` = nextLevelSumWithoutNode
}
}
}
return root
}
}
复杂度剖析：
- 时刻复杂度：O(n)O(n) 其间 n 为二叉树的节点总数，每个节点最多拜访 2 次（含入队 1 次）；
- 空间复杂度：O(n)O(n) BFS 队列空间。
类似标题：
- 993.二叉树的堂兄弟节点
2621. 规划能够求最短途径的图类（Hard）
标题地址
leetcode.cn/problems/de…
标题描绘
给你一个有n个节点的有向带权图，节点编号为0到n - 1。图中的初始边用数组edges表示，其间edges[i] = [fromi, toi, edgeCosti]表示从fromi到toi有一条价值为edgeCosti的边。
请你实现一个Graph类：
-
Graph(int n, int[][] edges)初始化图有n个节点，并输入初始边。 -
addEdge(int[] edge)向边会集增加一条边，其间****edge = [from, to, edgeCost]。数据保证增加这条边之前对应的两个节点之间没有有向边。 -
int shortestPath(int node1, int node2)回来从节点node1到node2的途径最小价值。假如途径不存在，回来1。一条途径的价值是途径中一切边价值之和。
问题剖析
这道题牵强能算 Floyd 算法或 Dijkstra 算法的模板题，先回顾一下最短路问题解决方案：
- Dijkstra 算法（单源正权最短路）：
- 实质上是贪心 + BFS；
- 负权边会损坏贪心策略的挑选，无法处理含负权问题；
- 稀少图小顶堆的写法更优，稠密图朴素写法更优。
- Floyd 算法（多源汇正权最短路）
- Bellman Ford 算法（单源负权最短路）
- SPFA 算法（单源负权最短路）
因为这道题需求支持多次查询操作，而 Floyd 算法能够缓存最短路成果，理论上 Floyd 算法是更优的挑选。不过，咱们观察到标题的数据量十分十分小，所以朴素 Dijkstra 算法也能通过。
题解一（朴素 Dijkstra）
这道题的查询操作是求从一个源点到目标点的最短途径，并且这条途径上没有负权值，符合 Dijkstra 算法的运用场景，在处理增加边时，只需求动态的修改图数据结构。
Dijkstra 算法的实质是贪心 + BFS，咱们需求将一切节点分为 2 类，在每一轮迭代中，咱们从 “候选集” 中挑选距离起点最短路长度最小的节点，因为该点不存在更优解，所以能够用该点来 “松懈” 相邻节点。
- 1、确认集：已确认（从起点开端）到当时节点最短途径的节点；
- 2、候选集：未确认（从起点开端）到当时节点最短途径的节点。
技巧：运用较大的整数 0x3F3F3F3F 代替整数最大值 Integer.MAX_VALUE 能够削减加法越界判别。
class Graph(val n: Int, edges: Array<IntArray>) {
private val INF = 0x3F3F3F3F
// 带权有向图（临接矩阵）
private val graph = Array(n) { IntArray(n) { INF } }
init {
// i 自旋的途径长度
for (i in 0 until n) {
graph[i][i] = 0
}
// i 直达 j 的途径长度
for (edge in edges) {
addEdge(edge)
}
}
fun addEdge(edge: IntArray) {
graph[edge[0]][edge[1]] = edge[2]
}
fun shortestPath(node1: Int, node2: Int): Int {
// Dijkstra
// 最短路
val dst = IntArray(n) { INF }
dst[node1] = 0
// 确认标记
val visited = BooleanArray(n)
// 迭代 n - 1 次
for (count in 0 until n - 1) {
// 寻觅候选会集最短路长度最短的节点
var x = -1
for (i in 0 until n) {
if (!visited[i] && (-1 == x || dst[i] < dst[x])) x = i
}
// start 可达的节点都拜访过 || 已确认 node1 -> node2 的最短路
if (-1 == x || dst[x] == INF || x == node2) break
visited[x] = true
// 松懈相邻节点
for (y in 0 until n) {
dst[y] = Math.min(dst[y], dst[x] + graph[x][y])
}
}
return if (INF == dst[node2]) -1 else dst[node2]
}
}
复杂度剖析：
- 时刻复杂度：O(m+q1⋅n2+q2)O(m + q_1n^2 + q_2) 其间 n 为节点数量，m 为边数量，q1q_1 为查询次数，q2q_2 为增加边次数。建图时刻 O(m)，每个节点拜访 n 次；
- 空间复杂度：O(n2+n)O(n^2 + n) 图空间 + 最短路数组
题解二（Dijkstra + 最小堆）
这道题是稠密图，朴素 Dijkstra 因为 Dijkstra + 最小堆。
朴素 Dijkstra 的每轮迭代中需求遍历 n 个节点寻觅候选会集的最短路长度。事实上，这 n 个节点中有部分是 ”确认集“，有部分是远离起点的边际节点，每一轮都遍历显得没有必要。咱们运用小顶堆记载候选会集最近深度的节点。
class Graph(val n: Int, edges: Array<IntArray>) {
private val INF = 0x3F3F3F3F
// 带权有向图（临接矩阵）
private val graph = Array(n) { IntArray(n) { INF } }
init {
// i 自旋的途径长度
for (i in 0 until n) {
graph[i][i] = 0
}
// i 直达 j 的途径长度
for (edge in edges) {
addEdge(edge)
}
}
fun addEdge(edge: IntArray) {
graph[edge[0]][edge[1]] = edge[2]
}
fun shortestPath(node1: Int, node2: Int): Int {
// Dijkstra + 最小堆
// 最短路
val dst = IntArray(n) { INF }
dst[node1] = 0
val heap = PriorityQueue<Int>() { i1, i2 ->
dst[i1] - dst[i2]
}
heap.offer(node1)
while (!heap.isEmpty()) {
// 运用 O(lgm) 时刻找出最短路长度
var x = heap.poll()
// 松懈相邻节点
for (y in 0 until n) {
if (dst[x] + graph[x][y] < dst[y]) {
dst[y] = dst[x] + graph[x][y]
heap.offer(y)
}
}
}
return if (INF == dst[node2]) -1 else dst[node2]
}
}
复杂度剖析：
- 时刻复杂度：O(m+q1⋅nlgm+q2)O(m + q_1nlgm+q_2) 其间 n 为节点数量，m 为边数量，q1q_1 为查询次数，q2q_2 为增加边次数。建图时刻 O(m)O(m)，每条边都会拜访一次，每轮迭代取堆顶 O(lgm)。这道题边数大于点数，朴素写法更优。
- 空间复杂度：O(n2+n)O(n^2 + n) 图空间 + 堆空间。
题解三（Floyd）
Fload 算法的实质是贪心 + BFS，咱们需求三层循环枚举中转点 i、枚举起点 j 和枚举结尾 k，假如 dst[i][k] + dst[k][j] < dst[i][j]，则能够松懈 dst[i][j]。
这道题的另一个关键点在于支持调用 addEdge() 动态增加边，所以运用 Floyd 算法时要考虑怎么更新存量图。
class Graph(val n: Int, edges: Array<IntArray>) {
val INF = 0x3F3F3F3F
// 途径长度（带权有向图）
val graph = Array(n) { IntArray(n) { INF } }
init {
// i 自旋的途径长度
for (i in 0 until n) {
graph[i][i] = 0
}
// i 直达 j 的途径长度
for (edge in edges) {
graph[edge[0]][edge[1]] = edge[2]
}
// Floyd 算法
// 枚举中转点
for (k in 0 until n) {
// 枚举起点
for (i in 0 until n) {
// 枚举结尾
for (j in 0 until n) {
// 比较 <i to j> 与 <i to p> + <p to j>
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j])
}
}
}
}
fun addEdge(edge: IntArray) {
val (x, y, cost) = edge
// 直达
graph[x][y] = Math.min(graph[x][y], cost)
// 枚举中转点
for (k in intArrayOf(x, y)) {
// 枚举起点
for (i in 0 until n) {
// 枚举结尾
for (j in 0 until n) {
// 比较 <i to j> 与 <i to k> + <k to j>
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j])
}
}
}
}
fun shortestPath(node1: Int, node2: Int): Int {
return if (graph[node1][node2] == INF) -1 else graph[node1][node2]
}
}
复杂度剖析：
- 时刻复杂度：O(m+n3+q1+q2⋅n2)O(m + n^3 + q_1 + q_2n^2) 其间 nn 为节点数量，mm 为边数量，q1q_1 为查询次数，q2q_2 为增加边次数。建图时刻 O(m+n3)O(m + n^3)，单次查询时刻 O(1)O(1)，单次增加边时刻 O(n2)O(n^2)；
- 空间复杂度：O(n2)O(n^2) 图空间。
相关标题：
- 743. 网络延迟时刻
近期周赛最短路问题：
- 2617. 网格图中最少拜访的格子数（Hard）
- 2612. 最少翻转操作数（Hard）
- 2608. 图中的最短环（Hard）
- 2577. 在网格图中拜访一个格子的最少时刻（Hard）
为了 Guardian 加油！
本文正在参与「金石方案」
