LeetCode 周赛 341 场,模拟 / 树上差分 / 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 $O(n + \alpha m)$2643.一最多的行(Easy)题目地址https://leetcode.cn/problems/row-with-maximum-ones/
题目描述给你一个大小为m x n
的二进制矩阵mat
,请你找出包含最多1的行的下标(从0开始)以及这一行中1的数目。
如果有多行包含最多的 1 ,只需要选择行下标最小的那一行。
返回一个由行下标和该行中 1 的数量组成的数组。
题解(模拟)简单模拟题。
class Solution { fun rowAndMaximumOnes(mat: Array): 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)题目地址https://leetcode.cn/problems/find-the-maximum-divisibility-score/
题目描述给你两个下标从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)题目地址https://leetcode.cn/problems/minimum-additions-to-make-valid-string/
题目描述给你一个字符串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)题目地址https://leetcode.cn/problems/minimize-the-total-price-of-the-trips/
题目描述现有一棵无向、无根的树,树中有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, price: IntArray, trips: Array): Int { // 建树 val graph = Array(n) { LinkedList() } 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>, 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 为根节点的子树的最大价格 private fun priceDfs(graph: Array>, 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, price: IntArray, trips: Array): Int { // 建树 val graph = Array(n) { LinkedList() } for (edge in edges) { graph[edge[0]].add(edge[1]) graph[edge[1]].add(edge[0]) } // 查询关系 val search = Array(n) { LinkedList() } 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>, val search: Array>) { // 并查集数据结构 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 为根节点的子树的最大价格 private fun priceDfs(graph: Array>, 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 }}
复杂度分析:
时间复杂度:$O(n + \alpha m)$ 其中 m 为 trips 数组的长度,$\alpha$ 是并查集的反阿克曼函数,近似于线性函数;空间复杂度:$O(n + m)$ 树空间 + DFS 递归栈空间,递归深度最大为 n。标签:
推荐文章
- 鲜切花扮靓产业振兴路!每年可实现总产值800余万元
- 研究人员最新发现 单个细胞可同时处理成百上千个信号
- 陆军第73集团军某旅 创新升级模拟训练器材
- 长期暴露在光照下性能退化 科学家发现钙钛矿太阳能电池最大缺陷
- 宁夏启动双百科技支撑行动 构建高水平产业创新体系
- 陆军炮兵防空兵学院 毕业学员综合战术演习现地备课工作圆满完成
- 国内首颗以茶叶冠名遥感卫星 安溪铁观音一号发射成功
- 区域特色产业转型升级 四川屏山以“3+”模式推进科技创新工作
- 激发创新动能促进产业发展 无锡滨湖走出产业转型“绿色”路
- 绥化全域低风险!黑龙江绥化北林区一地调整为低风险
- 走访抗美援朝纪念馆:长津湖的寒冷,与战斗一样残酷
- 节后第一天北京白天晴或多云利于出行 夜间起秋雨或再上线
- 走近网瘾少年们:他们沉迷网络的病根何在?
- “双减”后首个长假:亲子游、研学游需求集中释放
- 获2021年诺奖的蛋白,结构由中国学者率先解析
- 他从一窍不通的“门外汉”,到重装空投“兵专家”
- 升旗、巡岛、护航标、写日志,他们一生守护一座岛
- 中国故事丨“沉浸式”盘点今年的教育好声音!
- 农业农村部:确保秋粮丰收到手、明年夏季粮油播种
- “双减”出台两个月,组合拳如何直击减负难点?
- 《山海情》里“凌教授”的巨菌草丰收啦
- 且看新疆展新颜
- 天山脚下,触摸丝路发展新脉动
- 160万骑手疑似“被个体户”?平台不能当甩手掌柜
- 网游新政下,未成年人防沉迷的“主战场”在哪?
- “辱华车贴”商家及客服被行拘,处罚要不放过每一环
- 沙害是自然界的恶魔,而他是荒沙碱滩的征服者
- 面对婚姻,“互联网世代”的年轻人在忧虑什么?
- IP类城市缘何吸引力强?玩法创新带动游客年轻化
- 国庆主题花坛持续展摆至重阳节
- 都市小资还是潮流乐享?花草茶市场呈爆发性增长
- 从1.3万元降到700元,起诉书揭秘心脏支架“玄机”
- 北京国庆7天接待游客超861万人次 冬奥线路受青睐
- 陈毅元帅长子忆父亲叮嘱:你们自己学习要好,就可以做很多事儿
- 报告显示:这个国庆假期,粤川浙桂赣旅游热度最高
- 中国科技人才大数据:广东总量第一,“北上”这类人才多
- 嘉陵江出现有记录以来最强秋汛
- 全国模范法官周淑琴:为乡村群众点燃法治明灯
- 线上教学模式被盯上,网络付费刷课形成灰色产业链
- 云南保山:170公里边境线,4000余人日夜值守
- 警方查处故宫周边各类违法人员12人
- 农业农村部:确保秋粮丰收到手、明年夏季粮油播种
- 受南海热带低压影响 海南海口三港预计停运将持续到10日白天
- 多地网友投诉遭遇旅游消费骗局,呼吁有关部门严查乱象
- 神经科学“罗塞塔石碑”来了:迄今为止最完整的大脑细胞图谱
- 汾河新绛段发生决口
- 陕西支援14省份采暖季保供用煤3900万吨
- 这场红色故事“云比拼”,穿越时空为我们指引方向
- 受琼州海峡封航影响 10月7日、8日进出海南岛旅客列车停运
- 辽宁省工信厅发布10月8日电力缺口橙色预警
- 广州10月8日至20日对所有从省外来(返)穗人员实施核酸检测
- 假期怎么过得这么快?国庆5.15亿人次出游,你咋过的?
- 国庆假期全国道路交通总体安全平稳有序
- 哈尔滨市南岗区爱达88小区将调整为低风险地区
- 新疆霍尔果斯市2例无症状感染者新冠病毒均为德尔塔变异株
- 百闻不如一见——北京大学留学生参访新疆
- 看,生机勃勃的中国
- 国庆假期中国预计发送旅客4.03亿人次
- 新疆兵团可克达拉市:195名密接者已全部隔离医学观察
- 山西平遥消防4天29次救援:拖着腿走路也要完成任务
- 国庆假期北京接待游客861.1万人次
- 冷空气自西向东影响中国大部地区 气温将下降4℃至6℃
- 新疆哈密市巴里坤县发生4.3级地震 震源深度9千米
- 国庆假期中国国内旅游出游5.15亿人次
- 公安部交管局:国庆假期日均出动警力18万余人次,5位交警辅警牺牲
- 受南海热带低压影响广东将暂别高温天气
- “数说”杭州无障碍改造:触摸城市“爱的厚度”
- 新疆霍尔果斯无症状感染者新冠病毒属德尔塔变异株 未发现高度同源的基因组序列
- 新疆伊犁州:妥善做好滞留旅客安置返回工作
- 国庆假期广西累计接待游客逾3611万人次 实现旅游消费272.41亿元
- 2021年MAGIC3上海市青少年三对三超级篮球赛落幕
- 新疆兵团第四师可克达拉市1名无症状感染者为餐饮从业人员
- 哥伦比亚遇上广州:洋茶人“云上”喫茶 传播中国茶“味道”
- 厦门同安区四区域调整为低风险 全市无中高风险地区
- 直径2米“面气球”亮相 山西首届“寿阳味道”美食大赛启幕
- 世界第一埋深高速公路隧道大峡谷隧道出口端斜井掘进完成
- 浙南沿海村村发展有妙招 搭乘共富快车打造“海上花园”
- 新疆霍尔果斯两例无症状感染者新冠病毒均属德尔塔变异株
- 南沙港铁路国庆假期不停工 力争今年年底开通
- 添加陌生人为好友 内蒙古两女子被骗126万
- 中国国庆假期出行热:数字改变“关键小事”
- 水能载物亦能“生金” 浙江遂昌山村以水为媒奔共富
- 铁路人国庆雨中巡查排险记:一身雨衣、一把铁锹保安全畅通
- 铁路迎返程高峰 西安局集团公司加开79趟高铁列车
- 受热带低压影响 琼州海峡北岸等待过海车辆排长龙
- 哈尔滨市学校有序恢复线下教学
- 哈尔滨一地风险等级调整为低风险
- 从进“培训班”到看《长津湖》
- 安徽黄山国庆假期迎客12万余人 旅游市场稳步复苏
- 山西解除持续近90小时的暴雨四级应急响应
- 科学拦峰错峰削峰 嘉陵江洪水过境重庆中心城区“有惊无险”
- 粤高速大湾区路段假期车流集中 跨珠江口通道尤甚
- 千年街区“非遗”风催热国庆假期本地游
- “颜值担当”里的中国,映照“万物和谐”新气象
X 关闭
资讯
X 关闭
行业动态
-
老牛湾长城:四代人的接力守望|观天下
- 老牛湾长城:四代人的接力守望|观天下
- 四川内江东兴:一株天冬带动中医药大健康产业蓬勃发展-全球今日讯
- 全球焦点!白萝卜怎么炒好吃家常做法大全
- 全国公共体育场馆开放使用典型案例名单公布,山东这家单位上榜
- 天天头条:从“绿色制造”到“智造绿色”:一个厂区的绿色转型
- 最新:辽宁省营口经济技术开发区临港工业区管委会走访中州期货
- 内蒙古阿拉善盟额济纳旗2023-05-15 08:57发布大风蓝色预警
- 阿里(BABA)达摩院自动驾驶团队全部并入菜鸟集团 从科技探索转入场景落地-天天看热讯
- 全球快资讯:我市25所学校榜上有名
- 环球快讯:港股异动 | 招金矿业(01818)涨超4%领涨黄金股 美国通胀继续降温但债务担忧升温 加息或临尾声关注黄金配置机会