LeetCode 周赛 341（2023/04/16）模拟、树上差分、Tarjan 离线 LCA、DFS-六虎

本文已收录到 AndroidFamily，技术和职场问题，请重视大众号 [彭旭锐] 发问。

大家好，我是小彭。

上周末有单双周赛，双周赛咱们讲过了，单周赛那天早上有事没参与，后边做了虚拟竞赛，然后整个人就欠好了。前 3 题十分简略，但第 4 题有点东西啊，差点就抛弃了。终究，被折磨了一个下午和一个大夜总算把第 4 题做出来了，除了新学的 Tarjon 离线算法，这道题还涉及到树上差分、前缀和、DFS、图论等基础常识，几度被折磨得想要抛弃。这种感觉，似乎和当年在 LeetCode 上做前 10 题的时分差不多哈哈。

加油吧，没有什么经历是随随便便能够取得的，默默努力，愿君共勉。

周赛纲要

2643.一最多的行（Easy）

简略模仿题，无需解说。

模仿： $O (nm)$

2644.找出可整除性得分最大的整数（Easy）

简略模仿题，和 Q1 几乎相同，这场周赛出的欠好。

模仿： $O (nm)$

2645.结构有用字符串的最少刺进数（Medium）

中等模仿题，不难。

模仿： $O (n)$

2646.最小化游览的价格总和（Hard）

这道题的考点十分多，难度也十分高。先把握暴力 DFS 的解法，再剖析暴力解法中重复核算的环节，终究推出树上差分和离线 Tarjan 算法。这道题十分十分复杂，

递归中递和归的思想，再了解一下：为什么你学不会递归？谈谈我的经历
并查集问题，不要错失：怎么运用并查集处理朋友圈问题？
差分数组问题，这个点还没有写，同系列的前缀和数组能够参考：运用前缀和数组处理 “区间和查询” 问题
题解 1：暴力 DFS $O (nm)$
题解 2：树上差分 + Tarjan 离线 LCA + DFS $\alpha m)$

LeetCode 周赛 341（2023/04/16）模拟、树上差分、Tarjan 离线 LCA、DFS

2643.一最多的行（Easy）

标题地址

leetcode.cn/problems/ro…

标题描绘

给你一个大小为m x n的二进制矩阵mat，请你找出包含最多1的行的下标（从0开端）以及这一行中1的数目。

假如有多行包含最多的 1 ，只需求挑选行下标最小的那一行。

回来一个由行下标和该行中 1 的数量组成的数组。

题解（模仿）

简略模仿题。

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)
    }
}

复杂度剖析：

时刻复杂度： $O (nm)$
空间复杂度： $O (1)$

2644.找出可整除性得分最大的整数（Easy）

标题地址

leetcode.cn/problems/fi…

标题描绘

给你两个下标从0开端的整数数组nums和divisors。

divisors[i]的可整除性得分等于满足nums[j]能被divisors[i]整除的下标j的数量。

回来可整除性得分最大的整数divisors[i]。假如有多个整数具有最大得分，则回来数值最小的一个。

题解（模仿）

简略模仿题。

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
    }
}

复杂度剖析：

时刻复杂度： $O (nm)$
空间复杂度： $O (1)$

2645.结构有用字符串的最少刺进数（Medium）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个字符串word，你能够向其间任何位置刺进 “a”、”b” 或 “c” 恣意次，回来使word有用需求刺进的最少字母数。

假如字符串能够由 “abc” 串联屡次得到，则以为该字符串有用。

题解（模仿）

保护当前状况与方针状况，当两个状况存在误差时，刺进误差的字符数。

class Solution {
    fun addMinimum(word: String): Int {
        val n = word.length
        var targetStatus = 0
        var index = 0
        var ret = 0
        while (index < n) {
            // 当前状况
            val curStatus = word[index] - 'a'
            // 刺进
            ret += (curStatus + 3 - targetStatus) % 3
            // 方针状况
            targetStatus = (curStatus + 1) % 3
            index++
        }
        ret += when (targetStatus) {
            0 -> 0
            1 -> 2
            2 -> 1
            else -> 0
        }
        return ret
    }
}

复杂度剖析：

时刻复杂度： $O (n)$
空间复杂度： $O (1)$

2646.最小化游览的价格总和（Hard）

标题地址

leetcode.cn/problems/mi…

标题描绘

现有一棵无向、无根的树，树中有n个节点，按从0到n - 1编号。给你一个整数n和一个长度为n - 1的二维整数数组edges，其间edges[i] = [ai, bi]表明树中节点ai和bi之间存在一条边。

每个节点都相关一个价格。给你一个整数数组price，其间price[i]是第i个节点的价格。

给定途径的价格总和是该途径上一切节点的价格之和。

另给你一个二维整数数组trips，其间trips[i] = [starti, endi]表明您从节点starti开端第i次游览，并经过任何你喜欢的途径前往节点endi。

在履行第一次游览之前，你能够挑选一些非相邻节点并将价格折半。

回来履行一切游览的最小价格总和。

问题剖析

剖析 1：标题的数据结构是树而不是图，所以节点之间的最短路是唯一的，不需求运用最短路算法。从节点 start 到节点 end 的最优途径是 start 到最近公共先人（LCA）+ 最近公共先人（LCA）到 end；

剖析 2：标题能够挑选将一些节点的价格折半，显然价格越高的节点越应该折半，或许拜访次数越多的节点越应该折半。所以咱们能够先对每个 trips[i] 跑一次 DFS，并统计每个节点的拜访次数 cnts[i]，将每个节点的价格更新为 prices[i] * cnts[i]

剖析 3：类似于 337. 打家劫舍 III，假如咱们挑选将节点 x 折半（偷盗），那么与 x 相邻的节点便不能折半（偷盗）：

假如 prices[x] 折半，那么 x 的最近子节点不能折半；
假如 prices[x] 不变，那么 x 的最近子节点能够折半，也能够不折半，挑选两种情况的更优解。

题解一（暴力 DFS）

依据问题剖析，咱们的算法是：

1、先枚举每种旅途，统计每个节点的拜访次数（一共跑 m 次 DFS）；
2、更新每个节点的价格权重为 prices[i] * cnts[i]；
3、恣意挑选一个节点为根节点跑一次 DFS，在每一层递归中经过子问题的解得出原问题的解，每个子问题的解有「折半」和「不折半」两种成果；
4、终究，依据根节点的问题求出终究解。

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])
        }
        // 统计节点拜访次数
        val cnts = IntArray(n)
        for (trip in trips) {
            cntDfs(graph, cnts, trip[0], trip[1], -1)
        }
        // 更新价格
        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：是否找到方针节点
    private fun cntDfs(graph: Array<LinkedList<Int>>, cnts: IntArray, cur: Int, target: Int, parent: Int): Boolean {
        // 终止条件（方针节点）
        if (cur == target) {
            cnts[cur]++
            return true
        }
        // 枚举子节点（树的特性：每个方向最多只会拜访一次，不需求运用 visit 数组）
        for (to in graph[cur]) {
            // 防止回环
            if (to == parent) continue
            // 未找到
            if (!cntDfs(graph, cnts, to, target, cur)) continue
            // 找到方针途径，不需求再查看其他方向
            cnts[cur]++
            return true
        }
        return false
    }
    // return：以 cur 为根节点的子树的最大价格 <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 折半
        )
        // 枚举子节点（树的特性：每个方向最多只会拜访一次，不需求运用 visit 数组）
        for (to in graph[cur]) {
            // 防止回环
            if (to == parent) continue
            // 子树成果
            val childRet = priceDfs(graph, price, to, cur)
            ret[0] += Math.min(childRet[0], childRet[1])
            ret[1] += childRet[0]
        }
        return ret
    }
}

复杂度剖析：

时刻复杂度： $O (nm)$ 其间 m 为 trips 数组的长度，每轮 DFS 的时刻是 $O (n)$ ，计数时刻为 $O (nm)$ ，打家劫舍 DFS 的时刻为 $O (n)$ ；
空间复杂度： $O (n + m)$ 树空间 + DFS 递归栈空间，递归深度最大为 n。

题解一的瓶颈在于 cntDfs 中的 m 次 DFS 查找，怎么优化？

预备常识：差分数组

在 cntDfs 中的每一次 DFS 查找中，咱们需求将 [start, end] 途径上的节点拜访次数 +1，这正好类似于在数组大将 [start, end] 区间的位置 + 1，契合 “差分数组” 的运用场景。咱们能够在树上做差分，再经过一次 DFS 查找中核算节点的拜访次数。

例如在示例 1 中，咱们的途径是 (0, 3)，那么途径相当于 [0] + [1,3]，针对这两条途径的差分为：

[0]：diff[0]++，diff[father[0]] —，即 diff[1] —
[1, 3]：diff[3]++，diff[father[1]] —，即 diff[2]—

那怎么核算拜访次数呢？跟差分数组相同，对差分数组核算前缀和就能够取得节点的拜访次数，咱们在归的进程中累加差分值，例如节点 1 的拜访次数就是 +1 + 1 – 1 等于 1 次。

题解二（树上差分 + Tarjan 离线 LCA + DFS）

考虑到游览途径列表是固定的，咱们能够运用 Tarjan 离线算法，预先求出一切游览途径端点的最近公共先人。反之，假如游览途径列表是动态的，那么离线算法就无能为力了，需求运用复杂度更高的在线算法。

参考资料：

LCA最近公共先人（Tarjan离线算法）
图论 LCA 最近公共先人

在题解一中，咱们需求花费 m 次 DFS 查找来处理 m 个 LCA 问题，Tarjan 算法的核心思路是在一次 DFS 查找的进程中处理一切 LCA 查询问题：

1、任选一个点为根节点，从根节点开端。
2、「递」的进程（分化子问题）：遍历该点 u 一切子节点 v，并符号这些子节点 v 已被拜访过，若是 v 还有子节点，回来 2 持续「递」；
3、「归」的进程：寻觅与 u 有查询联系的点 k。假如 k 节点已经被拜访过，那么 u 和 k 的最近公共先人就是当前 u 和 k 所在的分组根节点；
4、节点 u 的问题完毕后，将节点 u 兼并到父节点的调集上。

细节阐明：Tarjan 算法递的进程是寻觅查询联系，当途径的两个端点都拜访过，那么这两个端点必然处在同一个分组中，而它们的分组根节点正好就是最近公共组件；

细节阐明：为什么分组根节点正好就是最近公共组件？由于归是按照 DFS 的查找顺序回归的；

细节阐明：怎么兼并 v 到 u 的调集上？这是并查集的操作，咱们界说 parent[x] 表明 x 节点的所处的分组，初始状况 parent[x] = x；

细节阐明：怎么查询与 u 有查询联系的点 k？预处理准备映射表；

细节阐明：为了区分阶段状况，咱们界说 color[x] 表明节点 x 的状况，0 表明未拜访、1 表明处于递归栈中，2 表明完毕。

更多细节，看代码吧。

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])
        }
        // 查询联系
        val search = Array(n) { LinkedList<Int>() }
        for (trip in trips) {
            search[trip[0]].add(trip[1])
            // 当途径两端相一起，防止重复
            if (trip[0] != trip[1]) search[trip[1]].add(trip[0])
        }
        val unionFind = UnionFind(n, graph, search)
        unionFind.tarjan(0, -1/* 无父节点 */)
        // 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>>) {
        // 并查集数据结构
        private val parent = IntArray(n) { it }
        // 树上的父节点
        private val father = IntArray(n)
        // Tarjan 状况
        private val colors = IntArray(n) //  表明未拜访、1 表明处于递归栈中，2 表明完毕
        // 树上差分
        val diff = IntArray(n)
        private fun find(x: Int): Int {
            // 途径紧缩
            if (x != parent[x]) parent[x] = find(parent[x])
            return parent[x]
        }
        // 这道题的兼并不能运用按秩兼并，必须将子节点 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) {
            // 记载父节点
            father[u] = fa
            // 符号已拜访
            colors[u] = 1
            // 递的进程：遍历 u 的一切子节点 v
            for (v in graph[u]) {
                if (0 != colors[v]) continue // 拜访过
                // 持续递的进程
                tarjan(v, u)
            }
            // 枚举查询联系
            for (k in search[u]) {
                if (k == u || colors[k] == 2) {
                    // 找到 u 和 k 的查询联系，更新树上差分
                    val lca = find(k)
                    diff[u]++
                    diff[lca]--
                    diff[k]++
                    val lcaParent = father[lca]
                    if (lcaParent >= 0) diff[lcaParent]--
                }
            }
            // 完毕
            colors[u] = 2
            if(fa != -1) merge(u, fa) // 将子节点 u 兼并到 fa 的调集中
        }
    }
    // return：以 cur 为根节点的子树的最大价格 <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])
        // 枚举子节点（树的特性：每个方向最多只会拜访一次，不需求运用 visit 数组）
        for (to in graph[cur]) {
            // 防止回环
            if (to == parent) continue
            // 子树成果
            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
    }
}

复杂度剖析：

时刻复杂度： $\alpha m)$ 其间 m 为 trips 数组的长度， $\alpha$ 是并查集的反阿克曼函数，近似于线性函数；
空间复杂度： $O (n + m)$ 树空间 + DFS 递归栈空间，递归深度最大为 n。

为了 Guardian 加油！

本文正在参与「金石计划」

LeetCode 周赛 341（2023/04/16）模拟、树上差分、Tarjan 离线 LCA、DFS

周赛纲要

2643.一最多的行（Easy）

标题地址

标题描绘

题解（模仿）

2644.找出可整除性得分最大的整数（Easy）

标题地址

标题描绘

题解（模仿）

2645.结构有用字符串的最少刺进数（Medium）

标题地址

标题描绘

题解（模仿）

2646.最小化游览的价格总和（Hard）

标题地址

标题描绘

问题剖析

题解一（暴力 DFS）

预备常识：差分数组

题解二（树上差分 + Tarjan 离线 LCA + DFS）

作者信息

推广

LeetCode 周赛 341（2023/04/16）模拟、树上差分、Tarjan 离线 LCA、DFS

周赛纲要

2643.一最多的行（Easy）

标题地址

标题描绘

题解（模仿）

2644.找出可整除性得分最大的整数（Easy）

标题地址

标题描绘

题解（模仿）

2645.结构有用字符串的最少刺进数（Medium）

标题地址

标题描绘

题解（模仿）

2646.最小化游览的价格总和（Hard）

标题地址

标题描绘

问题剖析

题解一（暴力 DFS）

预备常识：差分数组

题解二（树上差分 + Tarjan 离线 LCA + DFS）

相关文章

导航: 嵌套导航图和 | MAD Skills

从零开始写一个操作系统 —— 4.qemu

为什么App独立开发最好别做日记、记账

Android 逆向之脱壳实战篇

作者信息

推广