大家好，歡迎來到小彭的 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)
Fload：O(m + n^3 + q_1 + q_2·n^2)

2618. 查詢網格圖中每一列的寬度（Easy）

題目位址

https://leetcode.cn/problems/find-the-width-of-columns-of-a-grid/description/

題目描述

給你一個下标從 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-of-an-array/description/

題目描述

定義一個數組 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/description/

題目描述

給你一棵二叉樹的根 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-calculator/

題目描述

給你一個有 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，如果 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 + 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）

LeetCode 雙周賽 102，送分場

2618. 查詢網格圖中每一列的寬度（Easy）

題目位址

題目描述

題解（模拟）

2619. 一個數組所有字首的分數（Medium）

題目位址

題目描述

題解（動态規劃）

2620. 二叉樹的堂兄弟節點 II（Medium）

題目位址

題目描述

題解（BFS）

2621. 設計可以求最短路徑的圖類（Hard）

題目位址

題目描述

問題分析

題解一（樸素 Dijkstra）

題解二（Dijkstra + 最小堆）

題解三（Floyd）

繼續閱讀

LeetCode 雙周賽 107（2023/06/24）滑動視窗與離散化

leetcode華為面試算法題-124. 二叉樹中的最大路徑和

IT網際網路行業的鄙視鍊是什麼樣的?你搞後端開發，人家說你隻會CRUD；你搞前端開發，人家說你切圖仔一個；你搞全棧開發，人

leetcode華為面試算法題-51. N 皇後

leetcode大廠面試經典算法題-111. 二叉樹的最小深度

我許你紅裝十裡，一裡相思入骨，繁華滿地，流年如詩不如你。Imakeyouredtenmiles,amileofAcaci

LeetCode 周賽上分之旅 #33 摩爾投票派上用場

Leetcode 劍指 Offer II 036. 字尾表達式

LeetCode 周賽上分之旅 #35 兩題坐牢，菜雞現出原形

終于學會反轉連結清單了｜leetcode206、nc78（cpp、java實作）

LeetCode952三部曲之二：小幅度優化(137ms-＞122，超39%-＞51%)

【編碼能力超越ChatGPT！揭秘華為新一代代碼大模型】AI奇點網7月30日報道丨去年7月，華為諾亞方舟實驗室旗下的語音

#python#算法#leetcode

#leetcode#今天的你會感謝曾經努力的自己聽奢香夫人，解回文序列！

LeetCode155:最小棧，最簡單的中等難度，時間100%，記憶體低于官方

LeetCode 周賽上分之旅 # 37 多源 BFS 與連通性問題