程序员打卡Day19：贪心算法与区间合并的代码题全解析

做了19天打卡之后我明显感觉到自己的学习节奏被彻底稳住了。今天这一套组合拳Day19依然是老三样三道代码题编号55到57、一段英语翻译练习、再加一组单词打卡。听上去平平无奇但真正坚持下来你会发现这种“代码英语单词”的混合式打卡恰恰是程序员碎片时间利用率最高的方案之一。这篇文章我先把今天的代码题完整拆一遍然后把英语翻译和单词打卡的心得也一起写清楚特别适合正在筹备春招秋招、或者想重建英语阅读能力的同学直接参考。1. 今天这一天的整体设计与思路拆解1.1 为什么把代码题、英语翻译、单词打卡放在同一天很多人一听到“打卡”就以为只是机械重复其实我这19天下来最大的体会是这三件事本质上是同一件事——都是训练大脑的精准匹配能力。写代码是在训练“问题描述→数据结构→算法模板”的匹配英语翻译是在训练“英文原文→中文表达→术语还原”的匹配而单词打卡则是在训练“词汇信号→语义含义”的即时反应。三件事共用一个大脑资源池把它们拆在不同的时间块里互相调剂反而比一天只刷八个小时代码更容易坚持。这也是我为什么把代码题放在早晨头脑最清醒的时段来完成把翻译练习安排在午休之后单词打卡则拆成早上、晚上两轮来背。第一道代码题如果卡在三十分钟以上我会果断先跳过标记成“稍后重做”。这不是逃避而是代码训练里特别重要的一条经验个别卡壳题消耗的时间和精力往往够你搞定三道简单题加一轮单词复习。用有限的自律去死磕一道没有思路的困难题是很多人坚持不下去的真正原因。1.2 这三道题在刷题路线里的位置55-57我目前的刷题顺序参考的是经典的面试高频题路线题目编号用的是代码随想录风格的题号映射。第55题、第56题、第57题都集中在“贪心算法”和“区间处理”这两个高频考察区域几乎是面试手撕代码环节的常客。第55题属于典型的“全局最优解是否可行”判断题核心是动态维护可达范围。第56题是区间问题里的模板题排序后一次遍历就能解决延伸版本极多。第57题属于第56题的变体多了插入操作实际工程里非常常见比如日历系统、时间轴合并。很多朋友做这三道题时会觉得它们只是“套模板”但真正吃透后你会发现贪心问题的难点根本不是模板本身而是你能不能快速证明某个局部策略确实能导向全局最优。后面我会把每道题的证明过程和判别方法都展开讲清楚。2. 三道代码题具体拆解从读题到AC的完整路径2.1 第55题跳跃游戏贪心这道题题面非常简单给定一个非负整数数组你初始位置在数组的第一个下标数组里的每个元素代表你在该位置可以跳跃的最大长度判断你能不能到达最后一个下标。我第一次看到这道题的直觉是用递归做深搜每一层都枚举所有可能的跳跃步数把所有路径都走一遍。这个思路理论上没错但最坏情况下是每个位置都跳得非常远分支数量爆炸代码提交之后大概率超时。后来我才意识到这题考察的根本不是路径模拟而是“群体可达范围”的扩张过程。核心思想其实是维护一个右边界变量maxReach遍历数组时不断用当前位置的下标加上能跳的长度去更新它同时检查当前位置是否仍然在可达范围内。如果某个下标已经超过了maxReach说明从前面的位置无论如何都到不了这里直接返回false。如果遍历结束maxReach已经覆盖到最后一个下标那就说明终点可达。用通俗的比喻来说这就像一群人一个接一个地往一个方向搭“跳板”每个人能搭的最远距离标记出来后面的人只要站在前人的跳板上继续往前搭就行。最关键的一点是你不需要告诉任何人具体怎么跳只需要知道“最远能接多远”。这种“只要边界在扩张就不管中间细节”的思路就是典型的贪心策略而且它的正确性可以用“如果一个位置可达那么它前面的所有位置必可达”这个递推关系来证明。2.2 第56题合并区间排序 线性扫描这道题要求把有重叠的区间合并比如[[1,3],[2,6],[8,10],[15,18]]应该合并成[[1,6],[8,10],[15,18]]。我第一次做这道题的时候吃了排序顺序的亏。如果区间没有提前排序合并的时候你得来回比对复杂度很容易退化成 O(n²)。而排序之后整个问题就顺理成章地变成了线性扫描。先按每个区间的左端点从小到大排序然后维护当前合并区间的左边界L和右边界R。每来一个新区间只需要判断它的左端点是不是小于等于当前的R如果是说明有重叠就把R更新成两者右边界的更大值如果不是说明当前合并区间的使命结束了把[L,R]加入结果集然后把新区间的左右端点赋给L和R。这里我踩过一个不大不小的坑排序时如果左右端点一样的两条记录到底用不用第二键值其实在这个问题里不需要只要左端点有序即可。对于完全相同的区间合并逻辑会自然处理成同一个结果。另外要注意区间合并过程里R的更新是取最大值不是简单覆盖这个细节写代码时特别容易写成直接赋值导致错误结果。贪心思想在这道题里的体现非常隐蔽为什么要排序因为只有让所有区间按照左端点有序才能保证你“当前看到左端点最小的未处理区间”一定就是合并链上的下一个元素这样一来一次遍历就能保证覆盖所有重叠情况。排序本身是贪心成立的前置条件很多人忽略了这一步严格的排序理由。2.3 第57题插入区间分类讨论 模拟这道题与第56题最大的区别是它已经给你一个无重叠、按区间起点升序排列的区间列表现在要插入一个新的区间插入之后仍然要保持无重叠且有序。最直接的做法是把新区间塞进列表里然后调用完整的手写排序合并逻辑这个思路可以AC但在时间复杂度和空间复杂度上都没占到便宜。更优雅的做法是直接遍历原来的区间列表把情况分成三类当前区间完全在新区间左边也就是cur.end new.start这种情况直接把cur加进结果集。当前区间完全在新区间右边也就是cur.start new.end这种情况意味着新区间可以插入了插入之后后面所有区间也直接按顺序加入结果集。当前区间与新区间存在重叠则需要把new的左右边界分别更新为min(new.start, cur.start)和max(new.end, cur.end)继续往下走。这个分类讨论的过程本质上是在模拟一个不断“被扩展”的新区间吞并老区间。我在手写这道题时初期总是纠结新区间到底插入到了哪个位置所以代码写得特别绕。后来我干脆写了一个merged标志位只要新区间已经插入过后面所有老区间都无脑加入结果集逻辑瞬间干净许多。这道题往往会被面试官当作“热热身”题用来考察候选人对边界条件的敏感度。因为无论你写得再快只要漏了cur.start new.end这种恰好的边界输出结果就会出错。所以这里我特别建议在写完主逻辑之后一定要补三个测试用例新区间位于最开头、位于最结尾、以及和每个区间都重叠三个用例过了基本就稳了。3. 代码题的算法细节补充与工具配置心得3.1 贪心算法的正确性证明思路说句实在话很多刷题攻略都忽略了“证明”这一步。贪心算法的难点不是敲代码而是你如何说服自己局部最优的累积就是全局最优。以第55题为例反证法很干净假设存在某个位置i无法到达但算法在最开始时认为可以从起点覆盖到某个更远位置。由于可达范围的扩张是连续的如果i不可达说明在它之前某个位置j已经超过maxReach算法会在j处停下并返回false这与“最远位置可达”矛盾。所以贪心边界持续扩张的策略是充分且必要的。第56题的证明要更温和一些排序后从左往右扫描每次合并都确保当前区间是“所有左端点小于等于R的区间的最小并集”于是结果集里的每个大区间都是不可再合并的极小单元。只要通过归纳法检查每一步的区间确实覆盖了这一块整体结论就成立。很多朋友觉得证明很费时间过了笔试就万事大吉。但后面在面试里一旦面试官追问一句“为什么你这么贪心就对”你会立刻被区别出来。我的建议是每道贪心题AC之后用五分钟写一段注释把自己能想到的证明思路写进去哪怕写得不严谨也比完全没有强得多。3.2 本地调试时的常用设置刷这三道题时我用的是 VS Code C但这里有一个真实存在的痛点C 在 VS Code 里默认没有代码提示尤其是vector、algorithm这类头文件里的API打半天的人很容易烦躁。我目前的解决方式是给 VS Code 安装 C/C 扩展并且在c_cpp_properties.json里准确配置好 includePath 和编译器路径。很多新手会在网上找各种配置模板但直接照搬常常失效因为每个人的 MinGW 安装路径不一样。最稳妥的办法是打开命令面板执行C/C: Edit Configurations (UI)让插件自动探测编译器路径再手动补充 includePath。另外我强烈建议在本地装一个精简的调试脚本用一个main.cpp写算法逻辑再写一个input.txt放测试用例通过重定向方式读入这样每次改数据就不需要重新编译时在终端里手动输入。需要注意的是如果编辑器自带的任务系统在编译时没有加入参数./main input.txt这种执行方式在 Windows 的 CMD 里可能被拦最好直接在 VS Code 终端里运行或者配置一个.vscode/tasks.json把 input 文件路径作为参数传进去。我现在一般是用 CLion 作为主力因为这类的配置省心很多但如果你只想干刷题这一件事轻量级方案其实完全够用。4. 英语翻译练习从“看懂”到“翻顺”的思路4.1 今天的翻译材料与翻译步骤今天翻译的段落取自一段关于分布式系统中一致性和可用性取舍的英文技术说明内容是讨论在分区发生时系统应当选择强一致还是高可用。这种技术类文本非常适合程序员日常练习因为词汇不偏门逻辑链条清晰对后续读英文文档的帮助是立竿见影的。我的翻译步骤很固定基本可以复制到任何一段技术英文中先通读原文把长句的主干划出来找主谓宾。技术英文最常出现的坑是主语和谓语之间插了一大段定语从句或者介词短语导致你读到后面忘了前面。这时候用括号把插入成分先括起来主干就清晰了。标出所有专业术语并且查证标准译法。比如 “consistency” 译成一致性、“availability” 译成可用性、“partition tolerance” 译成分区容忍性这些术语不能乱造。按照中文表达习惯调整语序英文多被动中文多主动英文多用从句中文习惯拆成短句。最后对照参考译文检查重点看术语是否统一、逻辑连接词是否自然。4.2 翻译过程中容易踩的坑英译中第一个坑是逐词直译。比如 “the system cannot guarantee both consistency and availability” 如果直译成“系统不能保证两者都一致性和可用性”中文完全读不通。应该处理成“系统无法同时保证一致性和可用性”。第二个坑是忽略隐含主语。技术文档里常常出现省略主语的被动语态翻译时需要补上“系统”或“节点”这样的主语。第三个坑是术语上下文漂移。同一个词在不同语境下要灵活处理比如 “failover” 在数据库场景里译作“故障转移”在负载均衡场景里可能是“失效切换”。如果你在整篇文章里只用一个译法有些段落读起来会非常生硬。所以我现在的翻译练习不只是“翻完就完”而是翻完之后回译一遍也就是把中文再翻回英文对比自己最初的翻译和原文之间的差别。这个回译流程能放大你对句式结构的敏感度坚持半个月就能看到明显的语感提升。5. 单词打卡今天背了什么、怎么记最牢5.1 今日单词清单结合翻译材料提取今天打卡的单词是十三个主要和系统设计、分布式理论相关。这里我直接列出几个高频词你会发现它们和上面提到的翻译材料有很强的呼应关系单词含义记忆锚点partition分区分割数据库分区、网络分区都用这个词可以和 “part” 联系latency延迟和 “later” 同源都在说“晚一点”throughput吞吐量“throu-” 表示穿过穿过一个管道的能力replica副本复制品读音很像“re-plic-a”重复复制的东西consensus共识“con-”表示共同“sens-”表示感觉共同的感觉quorum法定人数分布式投票机制里必须凑齐的最小票数fault故障常见短语 fault-tolerant容错tolerate容忍容忍系统出错而不是消灭出错stale陈旧的读到了旧数据叫 stale readdurable持久的和 “during” 相关持续存在idempotent幂等的同一个操作执行多次结果相同backpressure背压系统处理不过来时反向传回的压力retry重试网络请求失败后的再来一次这组词如果只是抄写记忆第二天基本忘掉一半。我用的是“语境固定法”每个单词不单独背而是把它放在一句今天翻译材料里的原句里记。比如背 “quorum” 的时候我脑子里回放的是 “the system requires a quorum of nodes to agree before committing a write”这样记下来的单词是活的下次碰到同样的场景就能直接用出来。5.2 单词复习的节奏安排在单词打卡这件事上我试过很多方法最后定格下来的节奏是上午背新词十五个晚上复习昨晚的十五个加今天早上的全新词组周末把一周所有词汇跑一遍拼写测试。严格来说这并不是复杂的记忆曲线但它非常容易执行。实际操作中我还用了一个“主动回忆”的技巧不看例句只看单词尝试说出它的核心意思和至少一个搭配想不起来的时候再翻例句。这个主动回忆本身是记忆的强化器比反复默写高效得多。至于要不要用记忆软件我个人的看法是工具可以辅助但不要被工具的学习算法绑架。如果你下班后状态极差那就直接打开单词表笔写一遍也好过打开软件却只在打卡形式主义对自己没有半点帮助。6. 常见问题与打卡避坑经验实录6.1 打卡过程中最常问的三个问题很多朋友在打卡群里问过我“代码题卡住了要不要看题解”我的答案是十五分钟内没有任何思路果断看题解看完题解之后立刻合上自己从头到尾重写一遍然后隔一天再独立做一次。这才叫吸取题解的思路否则就成了背代码。“翻译练习要每天做吗感觉工作量好大。”要但不必贪多每天翻译一短段就好。你可以选技术博客的引言部分或者英文文档的“Overview”段落。重点是保持语感和术语敏感度而不是追求翻译体量。“单词打卡总是记不牢怎么办”记不牢的根本原因是缺乏语境。你今天背了十个单词如果不用它们去造句、去阅读、去翻译它们在你脑子里就没有连接点。所以最理想的搭配是把单词打卡和翻译练习放在同一天互相提供语境支撑。6.2 近期打卡踩过的坑与解决方案打卡近三周我踩过三个典型的坑这里如实分享一下。第一个坑是想在一次打卡里塞进太多内容代码题想刷三道、翻译想翻三段、单词想背三十个。结果就是每件事都没做好到晚上复盘时充满挫败感。解决方案是下调每天的期望值只追求可完成且可持续的量今天二十五分钟做完的题就是好题能坚持一百天的粒度才是正确的粒度。第二个坑是忽视回顾。一开始我每天只顾着往前赶进度从 Day1 一路打卡到 Day19学新知识点的时候忘旧知识点结果遇到同类型题目时又仿佛第一次见。现在我每天固定抽出十五分钟浏览前几天的打卡错题和翻译笔记这个“回头看的动作”不稳定但效果极其显著。第三个坑是只输入不输出。刷题代码只在本地运行成功就算完事翻译译文只在本地写完就算完事单词只在笔记里过一遍就算完事。后来我尝试每周把这周做过的三道典型题目整理成一篇带注释的题解发到自己的博客上或群里翻译材料里积累的好句子也顺手写成一小段总结。这个输出动作会迫使你把这些内容真正“过脑子”记忆效果比闷头输入好得多。6.3 打卡三件套对面试准备的实际价值最后再说说这套组合拳对我面试准备的帮助。代码题训练的其实是面试手撕代码环节的临场反应能力但很多候选人只练题不练表达。这一点我和翻译练习放在一起之后反而意外地解决了因为翻译要求你用中文把复杂概念讲清楚这不正是技术面试里“讲思路”的能力吗在我自己的中文表达里长期的翻译练习让我更习惯先总后分、先结论后解释的叙述方式。后来我把这个经验搬到了英语面试场景中先概括思路再逐步展开细节。这样即使代码写到一半卡住了面试官也清楚你的逻辑框架是什么评分标准就会宽松许多。如果你也想尝试这种组合式打卡我强烈建议从“代码题一道 翻译短段 单词五个”这种最小单位开始连续坚持一周以后再加量。这种渐进式叠加才是让打卡成为习惯、而不是成为负担的唯一路径。