本文已收录到 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)

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd


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

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd

题解(模仿)

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) 其间 nnmm 为 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]的分数。

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd

题解(动态规划)

简略动态规划题,简单发现递归联系:

  • 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) 其间 nnarrarr 数组的长度,每个节点最多拜访 1 次;
  • 空间复杂度:O(1)O(1) 不考虑成果数组。

2620. 二叉树的堂兄弟节点 II(Medium)

标题地址

leetcode.cn/problems/co…

标题描绘

给你一棵二叉树的根root,请你将每个节点的值替换成该节点的一切堂兄弟节点值的和

假如两个节点在树中有相同的深度且它们的父节点不同,那么它们互为堂兄弟

请你回来修改值之后,树的根**root**。

注意,一个节点的深度指的是从树根节点到这个节点通过的边数。

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd

题解(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个节点的有向带权图,节点编号为0n - 1。图中的初始边用数组edges表示,其间edges[i] = [fromi, toi, edgeCosti]表示从fromitoi有一条价值为edgeCosti的边。

请你实现一个Graph类:

  • Graph(int n, int[][] edges)初始化图有n个节点,并输入初始边。
  • addEdge(int[] edge)向边会集增加一条边,其间****edge = [from, to, edgeCost]。数据保证增加这条边之前对应的两个节点之间没有有向边。
  • int shortestPath(int node1, int node2)回来从节点node1node2的途径最小价值。假如途径不存在,回来1。一条途径的价值是途径中一切边价值之和。

LeetCode 双周赛 102(2023/04/15)模拟、BFS、Dijkstra、Floyd

问题剖析

这道题牵强能算 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 加油!

本文正在参与「金石方案」