1. 整页拆解为什么这四件事值得放在同一个晚上完成说实话如果要我从历年的学习笔记里挑出最值得拿出来聊聊的一天1月26日这天大概率会当选。原因很简单这天我同时啃下了约瑟夫环、整除的尾数、回文质数这三类算法题顺手还完成了计算机英语第12单元Section A前三段的翻译内容跨度足够大但彼此的底层逻辑又高度一致——都是在训练把问题翻译成程序逻辑的能力只不过一个翻译的对象是数学规律另一个翻译的对象是英文文本。很多人刷题有个误区今天只刷链表明天只写DP看似很努力实际上一遇到综合问题就卡壳。我当天的安排刻意避开了单一专题而是把模拟类问题和数论类问题混在一起做。约瑟夫环本质是一个环形数据结构的删除模拟整除的尾数是一个简单的枚举匹配问题回文质数则把回文判定和素数判定叠加在一起。三者的共同点在于它们都不是那种需要高深算法的难题而是需要你把边界条件想清楚、把暴力思路优化到可接受范围的中等题。这类题恰恰是笔试和面试中最常见的题型。至于计算机英语翻译很多人的第一反应是这跟算法有什么关系。但你仔细想想当你需要阅读英文报错信息、查阅官方文档、理解开源项目的README时你做的事情本质上就是把英文翻译成自己能理解的中文问题描述。我在翻译第12单元Section A时明显感觉到那些关于计算机体系结构、操作系统基础的专业词汇和我当天写的算法题并不冲突——它们都是编程素养的一部分。这篇内容我会分三个算法题逐一拆解每个题都给出完整的思路推导、代码实现、常见坑点然后把翻译部分的处理原则和前三段的具体译文也放进来。你可以把它当作一份可复现的练习记录也可以当作一个题目清单避坑指南来用。适合正在准备算法笔试的自学者也适合计算机专业需要过英语课的学生。2. 约瑟夫环从模拟删除到数学递推再到双向跳跃变种2.1 经典问题与最初级的链表模拟约瑟夫环的描述很经典n个人围成一圈从某个位置开始报数报到m的人出圈然后从下一个人重新开始直到剩下最后一个人求这个人的编号。我第一次接触这题时第一反应就是用循环链表模拟。创建一个环形链表每个节点代表一个人每次遍历m次删掉当前节点再继续。这个思路完全正确而且对n和m都比较小的场景比如n100m10运行速度完全没问题。代码写起来也简单核心循环就是走到目标节点前一个位置绕过它然后从下一个节点继续。但有一个细节很多新手会踩坑删除节点后下一次报数的起点是删除节点的下一个节点而不是从被删除节点本身开始。换句话说你维护的当前指针应该指向删除节点的后继而不是指向已经失去意义的被删除节点。我在最初写链表版约瑟夫环时就因为没有处理好这个指针更新次序导致结果总是差一位排查了很久才发现问题出在这里。2.2 数学递推为什么能从O(nm)降到O(n)当n和m都很大的时候链表模拟的时间复杂度O(nm)就会开始发痛。比如n100万、m100万你不可能真的去一圈圈地遍历。这时候就要用数学方法直接推导幸存者的位置。经典的做法是从最终状态倒推。设f(n)表示n个人围成一圈时幸存者的编号从0开始计数第一次报数出圈的是编号(m-1) mod n那个人。出圈后剩下的人在逻辑上重新形成一个长度为n-1的环而下一个报数起点是原来编号为m mod n的人。这时候关键的观察是n-1人问题的解f(n-1)对应的位置和它在n人环中的真实编号之间有一个固定的偏移m。用公式表示就是f(n) (f(n-1) m) % n f(1) 0这个公式很多人都背过但真正理解它的人不多。我建议你亲手推一遍假设n5m3手动模拟出出圈顺序然后从最后一轮只剩一个人开始往前反推看看每一步加m再取模的意义。只有亲手推过一遍你才不用死记公式。有了递推式后代码非常简洁。递归版很容易写但要注意当n超过一定规模时递归深度可能过大我用迭代版更稳def josephus(n, m): pos 0 for i in range(2, n 1): pos (pos m) % i # 题目如果要求从1开始编号这里加1返回 return pos 1这个循环的时间复杂度是O(n)空间复杂度是O(1)可以说已经是经典问题的标准答案了。2.3 双向跳跃约瑟夫环新增的隐藏考点最近在一些刷题社区里出现了一个变种词汇——双向跳跃约瑟夫环。这名字听起来唬人实际上是在经典约瑟夫环基础上加了一个反向规则每次报数方向交替变化比如第一次顺时针报数第二次逆时针报数第三次又顺时针。这种变种题我在实际笔试里见过两次一次是在某厂实习笔试另一次是在一个开源项目的算法挑战里。为什么出题人喜欢改这个方向因为经典约瑟夫环的数学递推法假设淘汰顺序是单向的一旦方向交替变化原来的f(n)递推公式就不能直接套用了。你需要回到模拟思路但是用更高效的数据结构——比如用平衡树或者带惰性删除的数组来维护当前还剩哪些人从而快速定位要删除的人。我当天的做法是先写了一个双向链表的双向遍历模拟版本把规则搞清楚确保逻辑正确然后针对n比较大的测试数据引入了懒删除线段树的做法线段树维护区间内剩余人数每次根据方向计算出目标序号然后在线段树里找到对应的真实位置。这个方案能把双向跳跃版本的时间复杂度压到O(n log n)实战中用起来很稳。2.4 当天的笔记里记了哪些坑这张表是我整理约瑟夫环相关问题时最常用的自查清单直接分享出来给你参考常见问题原因分析解决办法出圈顺序总差一位删除节点后指针没有移动到下一个起点在删除前先记录后继节点再删除最后把指针指向后继数学法算出的编号和模拟不一致起始编号没对齐0起始和1起始混用推公式时统一用0起始返回时再按题目要求加偏移双向跳跃版本用原公式套方向反转破坏了递推规则改用双向链表模拟或确定方向后用线段树维护位置m特别大导致模拟超时每次移动m步太慢用取模运算直接跳过整圈让m对当前剩余人数取余第4条尤其关键。经典模拟里你不需要真的移动m步因为一圈要走n步而m可能远远大于n所以每次移动 m mod n 步就足够了。加上这个优化后即使m很大模拟速度也能快很多倍。3. 整除的尾数一道考验边界条件的小题3.1 题面到底在问什么整除的尾数是很多刷题平台上的入门数论题。典型描述是给出两个整数a和b要求找出所有可能的n位数通常n是2或3使得某个数的最后n位等于b并且这个数整体能被a整除。换个更具体的版本就是有一个未知数形如 ( \text{prefix} \times 10^n b )其中prefix可以是0到某个上限之间的整数问哪些组合能让这个未知数被a整除。听起来很简单但它考察的重点从来不是数学定理而是你对尾数和前导零这些细节的处理。比如要求n2那么尾数b可能是一个两位数也可能是04这种带前导零的形式。如果你把结果当作整数处理就很容易丢掉前导零导致输出格式不对。3.2 暴力枚举法和它的优化空间最直接的思路是枚举。以常见版本给定一个四位数前缀m要求最后两位是b找所有能被a整除的数为例做法是让prefix从0循环到一个合理的最大上限对每个prefix构造完整数x prefix * 100 b然后检查x % a是否为0。循环上限取决于题目给定的百位千位范围比如有的题要求结果是一个四位数那prefix就只能从10循环到99也就是1000到9999之间的数。暴力枚举的问题是如果范围大比如要求找8位数单纯从0到99999999循环就不是最优了。更高效的做法是反过来思考先枚举余数。设未知数x的最后两位固定为b则x可表示为 k×100 b我们要找的是满足 (k×100 b) % a 0 的k。可以先把b对a取余设 r b % a然后找所有使 (k×100) % a (a - r) % a 的k。这一步看起来绕实际只是把取模运算的性质用了一下。不过以我刷题的经历来看大多数整除尾数题的范围都很小暴力枚举完全够用。真正容易丢分的地方是输出格式和边界值。比如前缀为0时能不能输出像00416这种带前导零的数再比如a为0要特殊处理——虽然大多数题会保证a0但加一个防御性判断永远不会错。3.3 一个小例子直接跑通假设题目要求所有的四位数末两位是52且能被8整除。那么x p × 100 52其中p从10到99。我直接跑了一遍循环输出符合条件的数。这里的关键是p不能从0开始因为p0时x52不是四位数p从1开始也不对因为p1时x152是三位数。只有p从10开始才能保证x大于等于1000。用Python写的话核心代码只有几行a, n 8, 2 # 除数尾数位数 tail 52 prefix_min 10 ** (n - 1) # 4位数n位尾数前缀至少10 # 实际n指尾数位数这里二位尾数时四位数要求前缀是100? 稍后说明等等这里我要明确一下术语四位数末两位是52里的末两位指的是n2而四位数的整体意味着前缀部分必须是两位数也就是10到99。如果要找的数是任意位数那前缀位数就不限只需要从0开始循环到一个足够大的值。做题时一定要先看清楚题面的位数限制。我当天做的版本是所有四位数于是prefix范围是range(10, 100)循环里检查 (prefix * 100 52) % 8 0。结果是这些数都能被8整除因为52本身能被4整除而100的倍数也天然是4的倍数进一步看8的整除规则需要百位及以上组合满足条件。这种题的关键不在于算法难度,而在于你有没有把四位数这个约束翻译成代码里的range起点。很多人就是从0开始枚举结果把小于1000的数也输出进去了被判错。3.4 做题时我用到的两个实用技巧第一个技巧是先用纸笔列几个极端输入再写代码。比如n1时尾数只有一位b0时x本身应该是谁的倍数都能满足a1时所有结果是自然数。把这些边界列在注释里基本可以避免低级错误。第二个技巧是当范围较大时可以按余数构造答案而不是逐个枚举。例如要在某个区间内找满足x % a 0且x的末两位固定为b的数可以先用区间起点和a算出第一个满足条件的数然后每a个数就会出现一个答案。这样计算量一下子就从O(区间长度)降到了O(答案个数)在区间上亿时非常有用。4. 回文质数把回文判定和素数判定揉在一起的好题4.1 基础概念回文和质数的双重判定回文质数也叫palprime就是从左往右读和从右往左读一样并且本身是质数的数。典型的有2、3、5、7、11、101、131等。这题的经典版本是输入一个范围输出该范围内的所有回文质数。这题看起来简单实际上暗藏两个性能陷阱。第一如果对每个数单独判素数在范围很大的时候会非常慢第二如果先生成范围内所有素数再筛回文又费内存且很多回文判断是冗余的。正确的思路取决于范围的大小和题目的时间限制。4.2 一个重要的数学结论偶数长度的回文数能被11整除这个结论太好用了除了11本身以外任何偶数位数的回文数都能被11整除因此它们不可能是质数。为什么因为一个偶数位数回文数奇数位数字之和与偶数位数字之和的差一定是0而11的整除规则恰恰要求这两个和的差能被11整除。0能被11整除所以整个数能被11整除。这个结论在职场上刷题时非常实用。它意味着你根本不需要检测夫如1221、9889这类六位数、八位数的偶数长度回文数——它们都是合数直接跳过即可。所以当你拿到区间[1, 10000000]时你实际要检测的只有奇数长度的回文数以及两位数的唯一特例11。这等于干掉了一半以上的候选数。4.3 结合素数筛的高效算法流程我当天的做法是分段处理。第一步如果给定的上限不大比如小于10的6次方直接用一个埃氏筛把区间内所有素数标记出来然后遍历筛表检查每个素数是否是回文。这个方法简单直接时间复杂度O(n log log n)对百万级别范围毫无压力。第二步如果范围更大比如到10的7次方以上光筛素数可能比较吃内存了就改为构造回文数试除法的思路。我先把区间分成两类偶数长度回文数一律跳过奇数长度回文数则通过构造的方式生成。例如要构造长度为2k1的回文数只需要枚举前k1位数字然后翻转前k位拼接到后面。这样生成的候选数数量大大减少然后再对这个候选数做质数判定用6k±1优化的试除法或者Miller-Rabin。一个额外的优化是回文质数的个位数不可能是偶数也不是5所以枚举时个位直接跳过这些数字。这个细节能把候选量再压缩到原来的40%左右时间节省非常明显。4.4 完整代码示例与踩坑记录我用Python写了一个百万级别的回文质数求解示例方便你对照理解def is_palindrome(num): s str(num) return s s[::-1] def sieve(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n ** 0.5) 1): if is_prime[i]: is_prime[i*i:n1:i] [False] * len(range(i*i, n1, i)) return is_prime limit 1000000 prime_flags sieve(limit) result [] for x in range(2, limit 1): if prime_flags[x] and is_palindrome(x): result.append(x) print(result[:20])注意这段代码里的切片赋值筛法虽然简洁但对于Python新手来说可能有点绕。如果不习惯可以用最朴素的for循环逐个标记。我一开始顺手用了切片写法结果在n特别大时内存占用有点高改回普通循环后就好了。另外这个代码在limit超过10的7次方时明显吃力所以在更大范围下我才换成构造回文数Miller-Rabin的方案。踩过的坑还有两个。第一个坑是中位数为0的情况。比如构造五位数10001它其实是回文数但明显能被101整除之类所以候选数构造出来后仍要做质数检测不能想当然。第二个坑是关于输出顺序。有些题要求按升序输出所有范围内的回文质数如果你先构造回文数再排序别忘了构造顺序可能不是天然升序尤其是在混合不同位数的时候。5. 计算机英语第12单元Section A前三段翻译的原则与实操5.1 计算机英语翻译不同于普通英语翻译很多同学一提到英语翻译就只知道查词、逐句抠语法但计算机英语的课文翻译有自己的特殊之处。第12单元Section A通常是关于计算机系统结构、操作系统或处理器架构之类的内容句子结构复杂专业术语密集。翻译的难点不在于把单词换成中文而在于把英文的逻辑链条完整地传达出来同时保留专业术语的准确含义。举个例子如果在课文里看到multiprogramming这个词你不能简单地译成多程序设计而要结合上下文判断它指的是操作系统的多道程序设计技术还是处理器层面的多程序并发。词义的选择取决于语境这是计算机英语翻译和文学翻译最大的不同。5.2 处理第1段的句子结构与术语策略以我当时处理的《计算机英语实用教程第4版》第12单元Section A第1段为例这段内容大体是在介绍计算机系统的层次结构或CPU的基本组成。英文原文通常会有很长的定语从句和并列结构翻译成中文时如果照着英文语序来句子就会变得很拗口。我的处理原则是先把句子的主干找出来即主语、谓语、宾语然后把修饰成分拆分变成短句。比如一个典型的英文长句可能这样写The control unit, which is responsible for directing the operation of the processor, determines the sequence in which instructions are executed. 如果硬译为控制单元它负责指挥处理器操作决定指令被执行序列就非常不自然。更好的处理是拆成两个中文短句控制单元负责指挥处理器的运作它决定指令的执行顺序。术语方面Processor译处理器control unit译控制单元instruction译指令sequence译顺序。这些词在计算机领域都有固定的译法不要随意改写成处理器件或者指令集之类可能引起歧义的表达。5.3 第2、3段中的被动语态和名词化结构第2、3段的典型难点是被动语态和名词化表达。英文科技写作特别喜欢用被动比如The data is transferred to the memory by the I/O controller和the execution of an instruction is divided into several stages。中文如果也机械地写成数据被传输到内存虽然能懂但不够地道。我会把被动转成主动或者直接使用由……完成的结构I/O控制器将数据传输到内存指令的执行可以被划分为若干阶段。名词化结构比如the generation of interrupts如果直译为中断的生成意思没错但中文里说产生中断更自然。翻译的时候要多考虑中文的动词优势把英文的名词短语改为动词短语。另外Section A里常有缩写词和专有名词第一次出现时会给出全称。按照教材的通行做法第一次出现时应该译出全称并保留英文缩写比如the arithmetic logic unit (ALU)译为算术逻辑单元ALU。这个细节在考试中可能会被当作评分点平时练习务必养成习惯。5.4 一段示范译文与对照注释下面是我当天做第1段翻译时的成品片段你可以对照着看原文大意The central processing unit is the core component of a computer system. It consists of the control unit, the arithmetic logic unit and a set of registers. The control unit directs the operation of the entire system by issuing control signals. The arithmetic logic unit performs arithmetic and logic operations on data.参考译文中央处理器是计算机系统的核心部件由控制单元、算术逻辑单元和一组寄存器组成。控制单元通过发出控制信号来指挥整个系统的运行。算术逻辑单元对数据执行算术与逻辑运算。这段看起来简单但里面有三个值得注意的翻译点。第一core component译为核心部件不要译成核心部分组成之类的病句。第二a set of registers中的a set of表示一组、一套不要丢掉数量概念。第三perform arithmetic and logic operations里面的perform不能用表演这种生硬的词而要用执行或进行。做完前三段之后我建议你做一个反向练习不看英文只凭中文译稿尽量回译成英文再和原文对照。这个过程能很快暴露出你对专业表达习惯的掌握程度比单纯反复读课文有用得多。6. 一天之内安排这些任务的时间分配与复习策略6.1 三个算法题和翻译可以交替进行有人可能觉得一天做三个算法题已经很累了还要抽时间翻译课文精力上会不会不够。以我的亲身体验来看把算法题和英语翻译交替进行反而效率更高。因为算法题需要高度集中连续做一个小时以后大脑容易疲劳这时切换到英语翻译本质上是一种不同模式的思考能让大脑得到休息同时又不浪费时间。我当天的实际时间安排大致是上午花大约40分钟解决约瑟夫环包括数学推导和写代码然后休息十几分钟用30分钟处理计算机英语Section A第1段的翻译下午分别做整除的尾数和回文质数两者都是90分钟以内搞定晚上再把第2、第3段译完最后统一核对一遍译文。整体下来总用时大约是三个多小时。6.2 错题记录和热词背后的延伸学习当天做完题后我在笔记里记录了三个关键收获约瑟夫环的递推要从1开始递推到n而不是从n递推到1回文质数的偶数长度回文数直接筛掉翻译时遇到缩写要保留英文全称。这三条是当天知识点的核心索引。关于双向跳跃约瑟夫环和计算机英语实用教程课后答案这两个热词我多说两句。前者是约瑟夫环的一个变种想拔高的同学可以在经典题做熟之后尝试手写双向链表版和线段树版后者则提醒我们计算机英语的课后答案只是底线真正的能力体现在脱离答案独立完成段落翻译。如果你只看答案不自己动手译考试时照样写不出流畅的专业译文。6.3 给不同基础读者的个性化建议对于刚接触算法的新手我建议第一遍做约瑟夫环和回文质数时不要强求最优解先把模拟做法和暴力做法写对再去看数学优化。确保能得出正确答案比一次写出最优解更重要。等基础扎实了再回头用线段树处理双向跳跃变种用构造回文数优化大范围搜索。对于已经有一定刷题量、以复试或面试为目标的人来说我反而建议把重心放在约瑟夫环的数学法推导上。面试官很可能不会直接问你约瑟夫环怎么解而是给你一个变形场景比如有n个人围成圈顺时针每隔k个人淘汰一人逆时针每隔m个人淘汰一人求最后幸存者。如果你把经典递推理解透彻遇到这类变形才不至于当场发懵。计算机英语部分无论你基础如何都要坚持自己先译一遍再对照参考译文。我见过太多人考试前疯狂背课文中文翻译结果试卷上稍微换一个句子就不知道如何组织语言。翻译能力不是背出来的是反复练出来的。我在实际操作中最深的一点体会是算法题和课文翻译放在同一天学习并不是一种低效混搭反而因为思维方式不同让大脑得到了活跃切换。不要总想着一次吃透一类知识学会在不同任务间自然过渡才是长期稳定学习的关键。最后再分享一个小技巧做算法题时把解题思路用中文写一遍再动手敲代码。这个过程很像做英语翻译——你先把题意翻译成算法步骤再把算法步骤翻译成代码。两件事其实是同一种核心能力练得越多手感越好。