ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

力扣 3635「最早完成陆地和水上游乐设施的时间 II」贪心公式题解 —— codeforces-go 仓库 O(n+m) 实现剖析

力扣 3635「最早完成陆地和水上游乐设施的时间 II」贪心公式题解 —— codeforces-go 仓库 O(n+m) 实现剖析 科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇指南以 leetcode/biweekly/162/c/README.md 为核心文档结合 c.go、c_test.go 与 c.txt 源码与测试数据完整讲解力扣双周赛 162 Q3题号 3635的贪心推导过程、O(nm) 时间 / O(1) 空间的线性解法以及该解法在当前仓库中如何落地为可测试、可复现的 Go 代码。读完本文你将掌握两类设施各选其一、先后顺序取最优这类贪心题的标准分析范式并能独立写出 Python / Java / C / Go 四种语言的正确实现。题目背景与题意解读本题出自力扣第 162 场双周赛 Q3题名为最早完成陆地和水上游乐设施的时间 IIEarliest Finish Time for Land and Water Rides II。仓库目录 leetcode/biweekly/162/ 中收录了本场四题的题解与实现其中目录a/对应的 Q1 题解 README 明确指出本题和 [3635] 是一样的见 leetcode/biweekly/162/a/README.md即 Q13634与 Q33635考察的是同一道题区别主要在于数据范围——II 版本要求用一次线性遍历完成求解不能依赖排序等额外开销。从解法公式可以还原题目等价语义你准备游玩一个陆地设施和一个水上设施每次只能玩其中一个第i个设施的最早可开始时间为startTime[i]游玩所需时长为duration[i]你可以选择先陆地、后水上或先水上、后陆地两种顺序目标是求出最早能够完成全部游玩的时间。仓库中 c.go 正是这一语义的直接实现earliestFinishTime分别计算两种顺序的答案并取最小值solve则负责单种顺序下的最早完成时间。贪心核心陆地完成得越早越好先分析先玩陆地设施、再玩水上设施这一顺序。贪心结论完成陆地游乐设施的时间越早越好——这样留给水上设施的余地越大整体完成时间越早。为什么可以这样贪设陆地游玩结束时刻为T则任一水上设施i的最早开始时间为$$ \max(\textit{waterStartTime}[i], T) $$其完成时间为$$ \max(\textit{waterStartTime}[i], T) \textit{waterDuration}[i] $$注意上式关于T单调不减T越大任一水上设施的完成时间只会更晚或持平。因此为了给后续水上设施创造最早的可能陆地阶段应选取完成时间最早的那一个陆地设施即$$ \textit{minFinish} \min_{i0}^{n-1} \textit{landStartTime}[i] \textit{landDuration}[i] $$这一步其实是一个标准的交换论证任何先玩一个并非最早完成的陆地设施的方案其陆地完成时刻T ≥ minFinish代入上式可知所有水上设施的完成时间都不会早于以minFinish为起点的方案因此不必枚举陆地设施的选择只需线性扫描取最小值。两种游玩顺序的公式推导先陆地、后水上陆地阶段最早完成时间minFinish上式水上阶段每个设施最早开始时间为max(waterStartTime[i], minFinish)因此水上阶段最早完成时间为$$ \min_{i0}^{m-1} \max(\textit{waterStartTime}[i],\textit{minFinish}) \textit{waterDuration}[i] $$记该结果为landWater。先水上、后陆地对于先玩水上游乐设施的情况计算方式同上原文档原文——只需把两组的startTime/duration对调完全复用同一套公式$$ \textit{waterLand} \min_{i0}^{n-1} \max(\textit{landStartTime}[i], \textit{minFinishWater}) \textit{landDuration}[i] $$其中minFinishWater min(waterStartTime[i] waterDuration[i])是水上阶段最早完成时间。最终答案取两种顺序的更优者$$ \textit{answer} \min(\textit{landWater},\ \textit{waterLand}) $$由于两组数据地位完全对称交换参数再调用同一函数是代码层面最简洁、最不易出错的实现方式这一点在原文档的四种语言解法中体现得淋漓尽致。复杂度分析时间复杂度$\mathcal{O}(nm)$。其中 $n$ 是landStartTime的长度$m$ 是waterStartTime的长度。每个数组各被完整扫描两次solve内部两轮循环最多被调用两次属于常数级别的两次线性扫描。空间复杂度$\mathcal{O}(1)$。除若干标量变量外不申请额外存储。这正是本题 II 版本所要求的能力在 $n,m$ 达到 $10^5$ 量级时依然可以轻松通过且无需排序、无需优先队列等额外数据结构。多语言实现以下四种语言实现均完整继承自 leetcode/biweekly/162/c/README.md并保持先定义单种顺序的solve再在入口函数中交换参数取最小值的统一结构。Python3class Solution: def solve(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) - int: min_finish min(start duration for start, duration in zip(landStartTime, landDuration)) return min(max(start, min_finish) duration for start, duration in zip(waterStartTime, waterDuration)) def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) - int: land_water self.solve(landStartTime, landDuration, waterStartTime, waterDuration) water_land self.solve(waterStartTime, waterDuration, landStartTime, landDuration) return min(land_water, water_land)Javaclass Solution { public int earliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) { int landWater solve(landStartTime, landDuration, waterStartTime, waterDuration); int waterLand solve(waterStartTime, waterDuration, landStartTime, landDuration); return Math.min(landWater, waterLand); } private int solve(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) { int minFinish Integer.MAX_VALUE; for (int i 0; i landStartTime.length; i) { minFinish Math.min(minFinish, landStartTime[i] landDuration[i]); } int res Integer.MAX_VALUE; for (int i 0; i waterStartTime.length; i) { res Math.min(res, Math.max(waterStartTime[i], minFinish) waterDuration[i]); } return res; } }Cclass Solution { int solve(vectorint landStartTime, vectorint landDuration, vectorint waterStartTime, vectorint waterDuration) { int min_finish INT_MAX; for (int i 0; i landStartTime.size(); i) { min_finish min(min_finish, landStartTime[i] landDuration[i]); } int res INT_MAX; for (int i 0; i waterStartTime.size(); i) { res min(res, max(waterStartTime[i], min_finish) waterDuration[i]); } return res; } public: int earliestFinishTime(vectorint landStartTime, vectorint landDuration, vectorint waterStartTime, vectorint waterDuration) { int land_water solve(landStartTime, landDuration, waterStartTime, waterDuration); int water_land solve(waterStartTime, waterDuration, landStartTime, landDuration); return min(land_water, water_land); } };Gofunc solve(landStartTime, landDuration, waterStartTime, waterDuration []int) int { minFinish : math.MaxInt for i, start : range landStartTime { minFinish min(minFinish, startlandDuration[i]) } res : math.MaxInt for i, start : range waterStartTime { res min(res, max(start, minFinish)waterDuration[i]) } return res } func earliestFinishTime(landStartTime, landDuration, waterStartTime, waterDuration []int) int { landWater : solve(landStartTime, landDuration, waterStartTime, waterDuration) waterLand : solve(waterStartTime, waterDuration, landStartTime, landDuration) return min(landWater, waterLand) }需要注意的几点实现细节初始值使用各语言对应的正无穷math.MaxInt/Integer.MAX_VALUE/INT_MAX保证min取值的正确性Go 版本使用 Go 1.21 引入的内置泛型函数min/max代码更简洁math.MaxInt来自标准库math包两侧数组通过zip/ 索引i并行访问保证startTime[i]与duration[i]一一对应。仓库源码与测试验证题解源码对照仓库中的 c.go 与 README 中的 Go 解法完全一致solve负责单种顺序earliestFinishTime交换参数取min。该文件同时是仓库一题一 Go 文件组织方式的体现——每个力扣题解目录包含README.md含完整推导与多语言代码、c.go最终提交版实现、c.txt离线测试用例与c_test.go由模板生成的测试入口。测试驱动模板自动生成用例c_test.go 由仓库的 LeetCode 模板自动生成文件头注明Generated by copypasta/template/leetcode/generator_test.go核心只有一段调用func Test_c(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, earliestFinishTime, c.txt, 0); err ! nil { t.Fatal(err) } }其中RunLeetCodeFuncWithFile的实现位于 leetcode/testutil/leetcode.go它读取c.txt按函数入参个数 返回值个数为一组tcSize : fNumIn fNumOut切分测试数据再逐组构造输入、调用被测函数并比对期望输出。也就是说只要c.txt中每fNumInfNumOut行构成一组输入 期望输出任何符合该签名的函数都能被自动批量测试。测试数据逐例验证c.txt 收录了两个官方样例我们逐一验证公式样例 1landStartTime[2,8]landDuration[4,1] waterStartTime[6]waterDuration[3] 期望输出9陆地最早完成min(24, 81) min(6, 9) 6先陆地后水上max(6, 6) 3 9先水上后陆地水上完成63 9再玩陆地min(max(2,9)4, max(8,9)1) min(13, 10) 10min(9, 10) 9✅样例 2landStartTime[5]landDuration[3] waterStartTime[1]waterDuration[10] 期望输出14陆地最早完成53 8先陆地后水上max(1, 8) 10 18先水上后陆地水上完成110 11再玩陆地max(5, 11) 3 14min(18, 14) 14✅两个样例恰好覆盖了先陆地更优样例 1与先水上更优样例 2两种情形验证了必须枚举两种顺序再取min的必要性。边界情况与易错点不要试图枚举每一对陆地 × 水上组合朴素的 $O(n \times m)$ 双循环在 $n,m$ 较大时必然超时贪心论证已经保证陆地阶段只需保留最早完成的那个设施minFinish水上阶段对waterStartTime的每个元素做一次max即可。顺序不可合并不能只算先陆地一种情况就返回因为当水上设施开始时间远早于陆地时先玩水上可能更优样例 2 正是如此。取min的初始值各语言需用最大可表示值初始化避免空比较或溢出错误C 中int范围内INT_MAX即安全上界。数据规模假设解法假设两组数组均非空题目保证至少各有一个设施若出现空数组公式中的min将退化为初始的极大值这一点与题目约束一致。延伸围绕该题的进阶练习原文档末尾附有作者整理的分类题单如何在分类题单中系统刷题的入口见 leetcode/biweekly/162/c/README.md其中与本题同类的主题包括贪心与思维基本贪心策略、反悔贪心、区间贪心、构造与脑筋急转弯——本题的越早越好与交换论证即属于这一类常用数据结构前缀和 / 差分 / 栈 / 队列 / 堆等——当贪心问题需要动态维护极值时例如在扫描过程中持续取min这些结构是常见配套工具滑动窗口与双指针适合练习在一次线性扫描中同时维护多个极值的编码能力。读者可以按上述主题循序渐进先吃透交换论证 枚举顺序取最优这一模式再扩展到更复杂的贪心优化问题。小结力扣 3635「最早完成陆地和水上游乐设施的时间 II」的核心是一道一次线性扫描即可求解的贪心题关键观察任一水上设施的完成时间关于陆地完成时刻单调不减故陆地阶段取min(startduration)即全局最优将两组数据视为对称交换参数复用同一个solve函数即可优雅地覆盖先陆地 / 先水上两种顺序时间复杂度 $O(nm)$、空间复杂度 $O(1)$是数据范围拉满时的标准答案。在 codeforces-go 仓库中这道题以 c.go c_test.go c.txt 三件套的形式沉淀为可复现、可回归的样例模板化的测试框架RunLeetCodeFuncWithFile更让写完即测成为仓库内每道题目的默认工作流。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 149 题解重排会议最大化空闲时间 II——「前三大空位 枚举会议」O(n) 贪心codeforces-go 仓库实战力扣双周赛 149 题解重排会议最大化空闲时间 II——「前三大空位 枚举会议」O n 贪心codeforces go 仓库实战 本篇文章完整拆解 L科学计算从模拟到 O(1) 公式力扣双周赛 144「石子移除游戏」完整题解与 codeforces-go 仓库实现剖析从模拟到 O 1 公式力扣双周赛 144「石子移除游戏」完整题解与 codeforces go 仓库实现剖析 导读 「石子移除游戏」Stone Remova科学计算力扣 3225 网格操作最大分数从 O(n^4) 超时到 O(n^2) 的 DP 优化全解codeforces-go 仓库实战力扣 3225 网格操作最大分数从 O n^4 超时到 O n^2 的 DP 优化全解codeforces go 仓库实战 导读 本文以 LeetCode科学计算上一篇如何用Scrutor简化.NET服务注册10个实用技巧帮你告别手动配置下一篇 探索高效工作流edgy.nvim 插件推荐创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表