本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。
大家好，欢送来到小彭的 LeetCode 周赛解题报告。
昨晚是 LeetCode 双周赛第 102 场，你加入了吗？这场较量比较简单，拼的是板子手速，继上周掉大分后算是回了一口血 。
2618. 查问网格图中每一列的宽度（Easy）
简略模拟题，无需解释。
- 模仿：$O(nm)$
2619. 一个数组所有前缀的分数（Medium）
简略动静布局题，简略到像模拟题。
- 动静布局：$O(n)$
2620. 二叉树的堂兄弟节点 II（Medium）
思考过程：递归→DFS→BFS。因为堂兄弟节点都在同一层，发现 “递归地缩小问题规模求解原问题” 和 DFS 都不好编码，而 BFS 更合乎 “层” 的概念。往 BFS 方向思考后，容易找到解决办法。
- BFS：$O(n)$
2621. 设计能够求最短门路的图类（Hard）
最近周赛的最短路问题十分多，印象中曾经间断呈现三次最短路问题。了解 Dijkstra 算法和 Floyd 算法的利用场景十分重要。
- 奢侈 Dijkstra：$O(m + q_1·n^2 + q_2)$
- Dijkstra + 最小堆：$O(m + q_1·nlgm+q_2)$
- Floyd：$O(m + n^3 + q_1 + q_2·n^2)$
2618. 查问网格图中每一列的宽度（Easy）
题目地址
https://leetcode.cn/problems/find-the-width-of-columns-of-a-g...
题目形容
给你一个下标从 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)$ 其中 $n$ 和 $m$ 为 grid 数组的行列大小，每个节点最多拜访 1 次；
- 空间复杂度：$O(1)$ 不思考后果数组。
2619. 一个数组所有前缀的分数（Medium）
题目地址
https://leetcode.cn/problems/find-the-score-of-all-prefixes-o...
题目形容
定义一个数组 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)$ 其中 $n$ 为 $arr$ 数组的长度，每个节点最多拜访 1 次；
- 空间复杂度：$O(1)$ 不思考后果数组。
2620. 二叉树的堂兄弟节点 II（Medium）
题目地址
https://leetcode.cn/problems/cousins-in-binary-tree-ii/descri...
题目形容
给你一棵二叉树的根 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)$ 其中 n 为二叉树的节点总数，每个节点最多拜访 2 次（含入队 1 次）；
- 空间复杂度：$O(n)$ BFS 队列空间。
类似题目：
- 993. 二叉树的堂兄弟节点
2621. 设计能够求最短门路的图类（Hard）
题目地址
https://leetcode.cn/problems/design-graph-with-shortest-path-...
题目形容
给你一个有 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 + q_1·n^2 + q_2)$ 其中 n 为节点数量，m 为边数量，$q_1$ 为查问次数，$q_2$ 为增加边次数。建图工夫 O(m)，每个节点拜访 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 + q_1·nlgm+q_2)$ 其中 n 为节点数量，m 为边数量，$q_1$ 为查问次数，$q_2$ 为增加边次数。建图工夫 $O(m)$，每条边都会拜访一次，每轮迭代取堆顶 O(lgm)。这道题边数大于点数，奢侈写法更优。
- 空间复杂度：$O(n^2 + n)$ 图空间 + 堆空间。
题解三（Floyd）
Fload 算法的实质是贪婪 + BFS，咱们须要三层循环枚举直达点 i、枚举终点 j 和枚举起点 k，如果 dsti + dstk < dsti，则能够松弛 dsti。
这道题的另一个关键点在于反对调用 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 + n^3 + q_1 + q_2·n^2)$ 其中 $n$ 为节点数量，$m$ 为边数量，$q_1$ 为查问次数，$q_2$ 为增加边次数。建图工夫 $O(m + n^3)$，单次查问工夫 $O(1)$，单次增加边工夫 $O(n^2)$；
- 空间复杂度：$O(n^2)$ 图空间。
相干题目：
- 743. 网络延迟时间
近期周赛最短路问题：
- 2617. 网格图中起码拜访的格子数（Hard）
- 2612. 起码翻转操作数（Hard）
- 2608. 图中的最短环（Hard）
- 2577. 在网格图中拜访一个格子的起码工夫（Hard）