LeetCode 周賽 341 場，模擬 / 樹上差分 / Tarjan 離線 LCA / DFS

大家好瓷式，我是小彭替饿。

上周末有單雙周賽，雙周賽我們講過了贸典，單周賽那天早上有事沒參加盛垦，后面做了虛擬競賽，然后整個(gè)人就不好了瓤漏。前 3 題非常簡單，但第 4 題有點(diǎn)東西啊颊埃，差點(diǎn)就放棄了蔬充。最后，被折磨了一個(gè)下午和一個(gè)大夜總算把第 4 題做出來了班利，除了新學(xué)的 Tarjon 離線算法饥漫，這道題還涉及到樹上差分、前綴和罗标、DFS庸队、圖論等基礎(chǔ)知識(shí)，幾度被折磨得想要放棄闯割。這種感覺彻消，似乎和當(dāng)年在 LeetCode 上做前 10 題的時(shí)候差不多哈哈。

加油吧宙拉，沒有什么經(jīng)驗(yàn)是隨隨便便能夠獲得的宾尚，默默努力，愿君共勉谢澈。

周賽大綱

2643. 一最多的行（Easy）

簡單模擬題煌贴，無需解釋。

模擬： $O(nm)$

2644. 找出可整除性得分最大的整數(shù)（Easy）

簡單模擬題锥忿，和 Q1 幾乎相同牛郑，這場周賽出的不好。

模擬： $O(nm)$

2645. 構(gòu)造有效字符串的最少插入數(shù)（Medium）

中等模擬題敬鬓，不難淹朋。

模擬： $O(n)$

2646. 最小化旅行的價(jià)格總和（Hard）

這道題的考點(diǎn)非常多笙各，難度也非常高。先掌握暴力 DFS 的解法瑞你，再分析暴力解法中重復(fù)計(jì)算的環(huán)節(jié)酪惭，最后推出樹上差分和離線 Tarjan 算法。這道題非常非常復(fù)雜者甲，

遞歸中遞和歸的思想春感，再理解一下：為什么你學(xué)不會(huì)遞歸？談?wù)勎业慕?jīng)驗(yàn)
并查集問題虏缸，不要錯(cuò)過：如何使用并查集解決朋友圈問題鲫懒？
差分?jǐn)?shù)組問題，這個(gè)點(diǎn)還沒有寫刽辙，同系列的前綴和數(shù)組可以參考：使用前綴和數(shù)組解決 “區(qū)間和查詢” 問題
題解 1：暴力 DFS $O(nm)$
題解 2：樹上差分 + Tarjan 離線 LCA + DFS $O(n + \alpha m)$

2643. 一最多的行（Easy）

題目地址

https://leetcode.cn/problems/row-with-maximum-ones/

題目描述

給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 mat 窥岩，請(qǐng)你找出包含最多 1 的行的下標(biāo)（從 0 開始）以及這一行中 1 的數(shù)目。

如果有多行包含最多的 1 宰缤，只需要選擇 行下標(biāo)最小 的那一行颂翼。

返回一個(gè)由行下標(biāo)和該行中 1 的數(shù)量組成的數(shù)組。

題解（模擬）

簡單模擬題慨灭。

class Solution {
    fun rowAndMaximumOnes(mat: Array<IntArray>): IntArray {
        var maxIndex = 0
        var maxCount = 0
        for (i in 0 until mat.size) {
            var count = 0
            for (j in 0 until mat[0].size) {
                count += mat[i][j]
            }
            if (count > maxCount) {
                maxCount = count
                maxIndex = i
            }
        }
        return intArrayOf(maxIndex, maxCount)
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nm)$
空間復(fù)雜度： $O(1)$

2644. 找出可整除性得分最大的整數(shù)（Easy）

題目地址

https://leetcode.cn/problems/find-the-maximum-divisibility-score/

題目描述

給你兩個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 和 divisors 朦乏。

divisors[i] 的 可整除性得分 等于滿足 nums[j] 能被 divisors[i] 整除的下標(biāo) j 的數(shù)量。

返回 可整除性得分 最大的整數(shù) divisors[i] 氧骤。如果有多個(gè)整數(shù)具有最大得分呻疹，則返回?cái)?shù)值最小的一個(gè)。

題解（模擬）

簡單模擬題筹陵。

class Solution {
    fun maxDivScore(nums: IntArray, divisors: IntArray): Int {
        var maxDivisor = 0
        var maxCount = -1
        for (divisor in divisors) {
            var count = 0
            for (num in nums) {
                if (num % divisor == 0) count++
            }
            if (count > maxCount || count == maxCount && divisor < maxDivisor) {
                maxDivisor = divisor
                maxCount = count
            }
        }
        return maxDivisor
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nm)$
空間復(fù)雜度： $O(1)$

2645. 構(gòu)造有效字符串的最少插入數(shù)（Medium）

題目地址

https://leetcode.cn/problems/minimum-additions-to-make-valid-string/

題目描述

給你一個(gè)字符串 word 刽锤，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次朦佩，返回使 word 有效需要插入的最少字母數(shù)并思。

如果字符串可以由 "abc" 串聯(lián)多次得到，則認(rèn)為該字符串有效吕粗。

題解（模擬）

維護(hù)當(dāng)前狀態(tài)與目標(biāo)狀態(tài)纺荧，當(dāng)兩個(gè)狀態(tài)存在偏差時(shí)，插入偏差的字符數(shù)颅筋。

class Solution {
    fun addMinimum(word: String): Int {
        val n = word.length
        var targetStatus = 0
        var index = 0
        var ret = 0
        while (index < n) {
            // 當(dāng)前狀態(tài)
            val curStatus = word[index] - 'a'
            // 插入
            ret += (curStatus + 3 - targetStatus) % 3
            // 目標(biāo)狀態(tài)
            targetStatus = (curStatus + 1) % 3
            index++
        }
        ret += when (targetStatus) {
            0 -> 0
            1 -> 2
            2 -> 1
            else -> 0
        }
        return ret
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$
空間復(fù)雜度： $O(1)$

2646. 最小化旅行的價(jià)格總和（Hard）

題目地址

https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/

題目描述

現(xiàn)有一棵無向宙暇、無根的樹，樹中有 n 個(gè)節(jié)點(diǎn)议泵，按從 0 到 n - 1 編號(hào)占贫。給你一個(gè)整數(shù) n 和一個(gè)長度為 n - 1 的二維整數(shù)數(shù)組 edges ，其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) ai 和 bi 之間存在一條邊先口。

每個(gè)節(jié)點(diǎn)都關(guān)聯(lián)一個(gè)價(jià)格型奥。給你一個(gè)整數(shù)數(shù)組 price 瞳收，其中 price[i] 是第 i 個(gè)節(jié)點(diǎn)的價(jià)格。

給定路徑的 價(jià)格總和 是該路徑上所有節(jié)點(diǎn)的價(jià)格之和厢汹。

另給你一個(gè)二維整數(shù)數(shù)組 trips 螟深，其中 trips[i] = [starti, endi] 表示您從節(jié)點(diǎn) starti 開始第 i 次旅行，并通過任何你喜歡的路徑前往節(jié)點(diǎn) endi 烫葬。

在執(zhí)行第一次旅行之前界弧，你可以選擇一些 非相鄰節(jié)點(diǎn) 并將價(jià)格減半。

返回執(zhí)行所有旅行的最小價(jià)格總和搭综。

問題分析

分析 1：題目的數(shù)據(jù)結(jié)構(gòu)是樹而不是圖垢箕，所以節(jié)點(diǎn)之間的最短路是唯一的，不需要使用最短路算法兑巾。從節(jié)點(diǎn) start 到節(jié)點(diǎn) end 的最優(yōu)路徑是 start 到最近公共祖先（LCA）+ 最近公共祖先（LCA）到 end条获；

分析 2：題目可以選擇將一些節(jié)點(diǎn)的價(jià)格減半，顯然價(jià)格越高的節(jié)點(diǎn)越應(yīng)該減半蒋歌，或者訪問次數(shù)越多的節(jié)點(diǎn)越應(yīng)該減半正什。所以我們可以先對(duì)每個(gè) trips[i] 跑一次 DFS喜鼓，并統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的訪問次數(shù) cnts[i]蹋宦，將每個(gè)節(jié)點(diǎn)的價(jià)格更新為 prices[i] * cnts[i]

分析 3：類似于 337. 打家劫舍 III古沥，如果我們選擇將節(jié)點(diǎn) x 減半（偷竊），那么與 x 相鄰的節(jié)點(diǎn)便不能減半（偷竊）：

如果 prices[x] 減半称诗，那么 x 的最近子節(jié)點(diǎn)不能減半；
如果 prices[x] 不變头遭，那么 x 的最近子節(jié)點(diǎn)可以減半寓免，也可以不減半，選擇兩種情況的更優(yōu)解计维。

題解一（暴力 DFS）

根據(jù)問題分析袜香，我們的算法是：

1、先枚舉每種旅途鲫惶，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的訪問次數(shù)（總共跑 m 次 DFS）蜈首；
2、更新每個(gè)節(jié)點(diǎn)的價(jià)格權(quán)重為 prices[i] * cnts[i]欠母；
3欢策、任意選擇一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)跑一次 DFS，在每一層遞歸中通過子問題的解得出原問題的解赏淌，每個(gè)子問題的解有「減半」和「不減半」兩種結(jié)果踩寇；
4、最終六水，根據(jù)根節(jié)點(diǎn)的問題求出最終解俺孙。

class Solution {
    fun minimumTotalPrice(n: Int, edges: Array<IntArray>, price: IntArray, trips: Array<IntArray>): Int {
        // 建樹
        val graph = Array(n) { LinkedList<Int>() }
        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }
        // 統(tǒng)計(jì)節(jié)點(diǎn)訪問次數(shù)
        val cnts = IntArray(n)
        for (trip in trips) {
            cntDfs(graph, cnts, trip[0], trip[1], -1)
        }
        // 更新價(jià)格
        for (i in 0 until n) {
            price[i] *= cnts[i]
        }
        // DFS（打家劫舍）
        val ret = priceDfs(graph, price, 0, -1)
        return Math.min(ret[0], ret[1])
    }

    // return：是否找到目標(biāo)節(jié)點(diǎn)
    private fun cntDfs(graph: Array<LinkedList<Int>>, cnts: IntArray, cur: Int, target: Int, parent: Int): Boolean {
        // 終止條件（目標(biāo)節(jié)點(diǎn)）
        if (cur == target) {
            cnts[cur]++
            return true
        }
        // 枚舉子節(jié)點(diǎn)（樹的特性：每個(gè)方向最多只會(huì)訪問一次辣卒，不需要使用 visit 數(shù)組）
        for (to in graph[cur]) {
            // 避免回環(huán)
            if (to == parent) continue
            // 未找到
            if (!cntDfs(graph, cnts, to, target, cur)) continue
            // 找到目標(biāo)路徑，不需要再檢查其他方向
            cnts[cur]++
            return true
        }
        return false
    }

    // return：以 cur 為根節(jié)點(diǎn)的子樹的最大價(jià)格 <cur 不變, cur 減半>
    private fun priceDfs(graph: Array<LinkedList<Int>>, price: IntArray, cur: Int, parent: Int): IntArray {
        val ret = intArrayOf(
            price[cur],     // x 不變
            price[cur] / 2 // x 減半
        )
        // 枚舉子節(jié)點(diǎn)（樹的特性：每個(gè)方向最多只會(huì)訪問一次睛榄，不需要使用 visit 數(shù)組）
        for (to in graph[cur]) {
            // 避免回環(huán)
            if (to == parent) continue
            // 子樹結(jié)果
            val childRet = priceDfs(graph, price, to, cur)
            ret[0] += Math.min(childRet[0], childRet[1])
            ret[1] += childRet[0]
        }
        return ret
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nm)$ 其中 m 為 trips 數(shù)組的長度荣茫，每輪 DFS 的時(shí)間是 $O(n)$ ，計(jì)數(shù)時(shí)間為 $O(nm)$ 场靴，打家劫舍 DFS 的時(shí)間為 $O(n)$ 啡莉；
空間復(fù)雜度： $O(n + m)$ 樹空間 + DFS 遞歸棧空間憎乙，遞歸深度最大為 n票罐。

題解一的瓶頸在于 cntDfs 中的 m 次 DFS 搜索，如何優(yōu)化泞边？

預(yù)備知識(shí)：差分?jǐn)?shù)組

在 cntDfs 中的每一次 DFS 搜索中该押，我們需要將 [start, end] 路徑上的節(jié)點(diǎn)訪問次數(shù) +1，這正好類似于在數(shù)組上將 [start, end] 區(qū)間的位置 + 1阵谚，符合 “差分?jǐn)?shù)組” 的應(yīng)用場景蚕礼。我們可以在樹上做差分，再通過一次 DFS 搜索中計(jì)算節(jié)點(diǎn)的訪問次數(shù)梢什。

例如在示例 1 中奠蹬，我們的路徑是 (0, 3)，那么路徑相當(dāng)于 [0] + [1,3]嗡午，針對(duì)這兩條路徑的差分為：

[0]：diff[0]++囤躁，diff[father[0]] —，即 diff[1] —
[1, 3]：diff[3]++荔睹，diff[father[1]] —狸演，即 diff[2]—

那怎么計(jì)算訪問次數(shù)呢？跟差分?jǐn)?shù)組一樣僻他，對(duì)差分?jǐn)?shù)組計(jì)算前綴和就可以獲得節(jié)點(diǎn)的訪問次數(shù)宵距，我們?cè)跉w的過程中累加差分值，例如節(jié)點(diǎn) 1 的訪問次數(shù)就是 +1 + 1 - 1 等于 1 次吨拗。

題解二（樹上差分 + Tarjan 離線 LCA + DFS）

考慮到旅行路徑列表是固定的满哪，我們可以使用 Tarjan 離線算法，預(yù)先求出所有旅行路徑端點(diǎn)的最近公共祖先劝篷。反之哨鸭，如果旅行路徑列表是動(dòng)態(tài)的，那么離線算法就力不從心了娇妓，需要使用復(fù)雜度更高的在線算法兔跌。

參考資料：

LCA最近公共祖先（Tarjan離線算法）
圖論 · LCA 最近公共祖先

在題解一中，我們需要花費(fèi) m 次 DFS 搜索來解決 m 個(gè) LCA 問題峡蟋，Tarjan 算法的核心思路是在一次 DFS 搜索的過程中解決所有 LCA 查詢問題：

1坟桅、任選一個(gè)點(diǎn)為根節(jié)點(diǎn)华望，從根節(jié)點(diǎn)開始。
2仅乓、「遞」的過程（分解子問題）：遍歷該點(diǎn) u 所有子節(jié)點(diǎn) v赖舟，并標(biāo)記這些子節(jié)點(diǎn) v 已被訪問過，若是 v 還有子節(jié)點(diǎn)夸楣，返回 2 繼續(xù)「遞」宾抓；
3、「歸」的過程：尋找與 u 有查詢關(guān)系的點(diǎn) k豫喧。如果 k 節(jié)點(diǎn)已經(jīng)被訪問過石洗，那么 u 和 k 的最近公共祖先就是當(dāng)前 u 和 k 所在的分組根節(jié)點(diǎn)；
4紧显、節(jié)點(diǎn) u 的問題結(jié)束后讲衫，將節(jié)點(diǎn) u 合并到父節(jié)點(diǎn)的集合上。

細(xì)節(jié)說明：Tarjan 算法遞的過程是尋找查詢關(guān)系孵班，當(dāng)路徑的兩個(gè)端點(diǎn)都訪問過涉兽，那么這兩個(gè)端點(diǎn)必然處在同一個(gè)分組中，而它們的分組根節(jié)點(diǎn)正好就是最近公共組件篙程；

細(xì)節(jié)說明：為什么分組根節(jié)點(diǎn)正好就是最近公共組件枷畏？因?yàn)闅w是按照 DFS 的搜索順序回歸的；

細(xì)節(jié)說明：如何合并 v 到 u 的集合上虱饿？這是并查集的操作拥诡，我們定義 parent[x] 表示 x 節(jié)點(diǎn)的所處的分組，初始狀態(tài) parent[x] = x氮发；

細(xì)節(jié)說明：如何查詢與 u 有查詢關(guān)系的點(diǎn) k袋倔？預(yù)處理準(zhǔn)備映射表；

細(xì)節(jié)說明：為了區(qū)分階段狀態(tài)折柠，我們定義 color[x] 表示節(jié)點(diǎn) x 的狀態(tài)，0 表示未訪問批狐、1 表示處于遞歸棧中扇售，2 表示結(jié)束。

更多細(xì)節(jié)嚣艇，看代碼吧承冰。

class Solution {
    fun minimumTotalPrice(n: Int, edges: Array<IntArray>, price: IntArray, trips: Array<IntArray>): Int {
        // 建樹
        val graph = Array(n) { LinkedList<Int>() }
        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }
        // 查詢關(guān)系
        val search = Array(n) { LinkedList<Int>() }
        for (trip in trips) {
            search[trip[0]].add(trip[1])
            // 當(dāng)路徑兩端相同時(shí)，避免重復(fù)
            if (trip[0] != trip[1]) search[trip[1]].add(trip[0])
        }
        val unionFind = UnionFind(n, graph, search)
        unionFind.tarjan(0, -1/* 無父節(jié)點(diǎn) */)

        // DFS（打家劫舍）
        val ret = priceDfs(graph, price, unionFind.diff, 0, -1)
        return Math.min(ret[0], ret[1])
    }

    // 并查集
    private class UnionFind(val n: Int, val graph: Array<LinkedList<Int>>, val search: Array<LinkedList<Int>>) {
        // 并查集數(shù)據(jù)結(jié)構(gòu)
        private val parent = IntArray(n) { it }

        // 樹上的父節(jié)點(diǎn)
        private val father = IntArray(n)

        // Tarjan 狀態(tài)
        private val colors = IntArray(n) //  表示未訪問食零、1 表示處于遞歸棧中困乒，2 表示結(jié)束

        // 樹上差分
        val diff = IntArray(n)

        private fun find(x: Int): Int {
            // 路徑壓縮
            if (x != parent[x]) parent[x] = find(parent[x])
            return parent[x]
        }

        // 這道題的合并不能使用按秩合并，必須將子節(jié)點(diǎn) x 合并到 y 的集合中
        private fun merge(x: Int, y: Int) {
            // 按秩合并
            val rootX = find(x)
            val rootY = find(y)
            if (rootX != rootY) parent[rootX] = rootY
        }

        fun tarjan(u: Int, fa: Int) {
            // 記錄父節(jié)點(diǎn)
            father[u] = fa
            // 標(biāo)記已訪問
            colors[u] = 1
            // 遞的過程：遍歷 u 的所有子節(jié)點(diǎn) v
            for (v in graph[u]) {
                if (0 != colors[v]) continue // 訪問過
                // 繼續(xù)遞的過程
                tarjan(v, u)
            }
            // 枚舉查詢關(guān)系
            for (k in search[u]) {
                if (k == u || colors[k] == 2) {
                    // 找到 u 和 k 的查詢關(guān)系贰谣，更新樹上差分
                    val lca = find(k)
                    diff[u]++
                    diff[lca]--
                    diff[k]++
                    val lcaParent = father[lca]
                    if (lcaParent >= 0) diff[lcaParent]--
                }
            }
            // 結(jié)束
            colors[u] = 2
            if(fa != -1) merge(u, fa) // 將子節(jié)點(diǎn) u 合并到 fa 的集合中
        }
    }

    // return：以 cur 為根節(jié)點(diǎn)的子樹的最大價(jià)格 <cur 不變, cur 減半>
    private fun priceDfs(graph: Array<LinkedList<Int>>, price: IntArray, diff: IntArray, cur: Int, parent: Int): IntArray {
        val ret = intArrayOf(0, 0, diff[cur])
        // 枚舉子節(jié)點(diǎn)（樹的特性：每個(gè)方向最多只會(huì)訪問一次娜搂，不需要使用 visit 數(shù)組）
        for (to in graph[cur]) {
            // 避免回環(huán)
            if (to == parent) continue
            // 子樹結(jié)果
            val childRet = priceDfs(graph, price, diff, to, cur)
            ret[0] += Math.min(childRet[0], childRet[1])
            ret[1] += childRet[0]
            ret[2] += childRet[2] // 累加前綴和
        }
        ret[0] += price[cur] * ret[2]
        ret[1] += price[cur] * ret[2] / 2
        return ret
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n + \alpha m)$ 其中 m 為 trips 數(shù)組的長度迁霎， $\alpha$ 是并查集的反阿克曼函數(shù)，近似于線性函數(shù)百宇；
空間復(fù)雜度： $O(n + m)$ 樹空間 + DFS 遞歸椏剂空間，遞歸深度最大為 n携御。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末昌粤，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子啄刹，更是在濱河造成了極大的恐慌涮坐，老刑警劉巖，帶你破解...
沈念sama閱讀 206,482評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件誓军，死亡現(xiàn)場離奇詭異袱讹，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)谭企，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門廓译，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人债查，你說我怎么就攤上這事非区。” “怎么了盹廷？”我有些...
開封第一講書人閱讀 152,762評(píng)論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵征绸，是天一觀的道長。經(jīng)常有香客問我俄占，道長管怠，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 55,273評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任缸榄，我火速辦了婚禮渤弛，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘甚带。我一直安慰自己她肯，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 64,289評(píng)論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布鹰贵。她就那樣靜靜地躺著晴氨，像睡著了一般。火紅的嫁衣襯著肌膚如雪碉输。梳的紋絲不亂的頭發(fā)上籽前，一...
開封第一講書人閱讀 49,046評(píng)論 1贊 285
城市分裂傳說
那天，我揣著相機(jī)與錄音，去河邊找鬼枝哄。笑死肄梨，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的膘格。我是一名探鬼主播峭范，決...
沈念sama閱讀 38,351評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼瘪贱！你這毒婦竟也來了纱控？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 36,988評(píng)論 0贊 259
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤菜秦，失蹤者是張志新（化名）和其女友劉穎甜害，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體球昨，經(jīng)...
沈念sama閱讀 43,476評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡尔店，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,948評(píng)論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了主慰。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片嚣州。...
茶點(diǎn)故事閱讀 38,064評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖共螺，靈堂內(nèi)的尸體忽然破棺而出该肴，到底是詐尸還是另有隱情，我是刑警寧澤藐不，帶...
沈念sama閱讀 33,712評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布匀哄，位于F島的核電站，受9級(jí)特大地震影響雏蛮，放射性物質(zhì)發(fā)生泄漏涎嚼。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,261評(píng)論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一挑秉、第九天我趴在偏房一處隱蔽的房頂上張望法梯。院中可真熱鬧，春花似錦犀概、人聲如沸立哑。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評(píng)論 0贊 19
一樁弒父案阱冶，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至滥嘴，卻和暖如春木蹬，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,486評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工镊叁，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留尘颓，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,511評(píng)論 2贊 354
代替公主和親
正文我出身青樓晦譬，卻偏偏與公主長得像疤苹，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子敛腌，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,802評(píng)論 2贊 345

LeetCode 周賽 341 場弄兜，模擬 / 樹上差分 / Tarjan 離線 LCA / DFS

LeetCode 周賽 341 場，模擬 / 樹上差分 / Tarjan 離線 LCA / DFS

周賽大綱

2643. 一最多的行（Easy）

題目地址

題目描述

題解（模擬）

2644. 找出可整除性得分最大的整數(shù)（Easy）

題目地址

題目描述

題解（模擬）

2645. 構(gòu)造有效字符串的最少插入數(shù)（Medium）

題目地址

題目描述

題解（模擬）

2646. 最小化旅行的價(jià)格總和（Hard）

題目地址

題目描述

問題分析

題解一（暴力 DFS）

預(yù)備知識(shí)：差分?jǐn)?shù)組

題解二（樹上差分 + Tarjan 離線 LCA + DFS）

推薦閱讀更多精彩內(nèi)容