刷题笔记这个系列写了挺多篇了今天轮到力扣第66题“加一”。说实话这道题在“力扣热题100”和各类“刷题攻略”里基本属于必刷的入门档难度标记是“简单”但我这些年见过不少人在这道题上翻车而且翻车姿势五花八门有人用转数字的方式爆了精度有人没处理全是9的边界直接WA还有人把数组长度给搞变了。我决定把这道题拿出来认真拆一遍把你可能踩的坑、面试时可能被追问的点、以及它背后真正想考察的东西全部讲透。这道题到底在问什么一句话给你一个用数组表示的非负整数比如digits [1,2,3]表示数字 123你把它的值加 1结果还得是数组形式也就是[1,2,4]。看起来人畜无害但越简单的题越能看出基本功。这篇文章适合三种人刚上手力扣、需要一份能直接照着理解写法的新手准备面试、想把边界和复杂度聊明白的求职者以及刷题有一阵子了、想顺便梳理一下同类题型的老手。1. 先把题目看明白不是“加一”那么简单1.1 题面描述与示例完整题目长这样给定一个由整数组成的非空数组所表示的非负整数在该数的基础上加一。最高位数字存放在数组的首位数组中每个元素只存储单个数字。你可以假设除了整数 0 之外这个整数不会以零开头。几个关键约束得圈出来数组非空所以不用处理空数组。每个元素是 0 到 9 的单个数字。数组第一个元素是最高位所以[1,2,3]是 123不是 321。除了数字 0 本身不会出现[0,1,2]这种前导零的表示。官方给了两个示例再加上一个要命的边界情况输入输出说明[1,2,3][1,2,4]123 1 124[4,3,2,1][4,3,2,2]4321 1 4322[9][1,0]9 1 10位数变多了[9,9,9][1,0,0,0]999 1 1000最麻烦的进位链前两个示例看起来毫无压力后两个才是真正的考点。你如果把这道题当成“遍历一遍最后一个元素加一”那[9]这个用例就会让你原地裂开。1.2 考点拆解数组、进位、边界这道题虽然短但考点一点不少。拆开来看第一数组遍历的顺序感。加法的进位是从低位往高位传递的对应到数组里就是从右往左。很多新手习惯从头往后遍历这在别的题目里可能没错但“加一”这种进位题从前往后你根本不知道后面会不会冒出一个进位把你当前这位也变成 0。第二进位的处理方式。正常的加法思维是维护一个carry变量当前位加上进位后取余、整除。但这道题有个特殊性它只加 1。所以进位只会从“9 1”产生而且一旦产生当前位就变成 0进位继续往前传。这意味着你可以不用显式carry变量直接判断当前位是不是 9 就够了。第三边界的扩容。如果每一位都是 9比如[9]、[9,9]、[9,9,9]那么加一之后位数会变多数组需要扩张。[9]变成[1,0][9,9]变成[1,0,0]。这一条在面试里几乎必问因为大多数人能处理普通情况但忘了最终的全 9 进位。第四原地修改的意识和语言特性。这道题最优解希望你在原数组上做修改而不是每次循环都 new 一个新数组。尤其像 Java 这种数组长度固定的语言遇到全 9 你还得知道怎么创建新数组并把1放在首位。1.3 为什么这道题能进“热题100”“力扣热题100”里收录的题不是单纯按难度排的而是按面试出现频率 知识点覆盖密度排的。“加一”能进这个榜单不是因为题目本身多难而是因为它用最少的代码覆盖了最基础的几个思维点数组遍历方向的选择、边界条件的穷举、原地操作的空间意识。你会发现凡是这类“看起来很简单但边界能玩出花”的题面试官尤其喜欢。为什么因为能在 5 分钟内写完并 AC 的人很多但能在 5 分钟内把思路讲清楚、把边界列全、把复杂度分析明白的人很少。你自己刷题的时候可能也觉得这题一次就过了没啥好说的。但在面试官眼里这道题是块试金石能试出你写代码是“背模板”还是“真理解”。2. 解法思路从直觉到正解的三条路径2.1 路径一转数字加完再转回新手最爱坑最多很多人看到这道题的第一反应是这还不简单把数组转成数字加一再转回数组就完事了。我第一次在力扣上做这道题写的就是这种解法代码大概长这样var plusOne function (digits) { let num parseInt(digits.join()); num 1; return String(num).split().map(Number); };在[1,2,3]上跑完美返回[1,2,4]。在[9]上跑parseInt(9) 1等于 10转回[1,0]好像也没问题。但力扣的判题器不讲武德它会在测试用例里给你塞一个大数组比如[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]这个数组转成数字是6145390195186705543。问题来了JavaScript 的Number类型安全整数范围是2^53 - 1也就是9007199254740991。超过这个范围精度就开始丢失。6145390195186705543远远超过安全范围parseInt出来的是一个被四舍五入的近似值。你加一之后再转回数组得到的结果就是错的而且错得毫无规律Debug 起来让人抓狂。Python 虽然没有这个精度问题Python 的整数是任意精度的但用 Python 写这条路的人照样会踩另一个坑int(.join(map(str, digits)))确实不会丢精度但如果你把结果再转回字符串去拆分遇到某些特殊情况比如数组很长你就得额外处理。更关键的是这违背了题目考察的初衷——它想让你操作数组而不是绕过数组去玩类型转换。这不是说转数字方案一无是处但它只适用于“数字范围很小、你可以确定不会溢出”的场景。做题和写业务代码一样第一原则是看清楚约束条件。力扣这道题没有明确说数组长度上限但按惯例测试用例会覆盖大数所以这种解法在面试里基本属于“面试官看了会摇头”的答案。2.2 路径二逆序遍历按位处理进位标准答案正确的解法思路特别朴素模拟手算加法。你手算 199 1 的时候不会先把 199 变成什么“整体数字”你是从个位开始9 1 10写 0 进 1十位 9 进上来的 1 10写 0 再进 1百位 1 1 2。这个过程翻译成代码就是class Solution: def plusOne(self, digits: List[int]) - List[int]: n len(digits) for i in range(n - 1, -1, -1): if digits[i] 9: digits[i] 1 return digits digits[i] 0 # 能走到这里说明所有位都是 9 return [1] [0] * n这个代码只有几行但每一行都有讲究。为什么从后往前遍历因为加法的进位方向是从低位到高位。数组末尾是个位开头是最高位所以必须从n-1往前走到0。为什么digits[i] 9就直接加一返回因为如果当前位不是 9加上 1 之后不会产生进位那后面的高位完全不受影响。比如[1,2,3]末位 3 变成 4直接返回[1,2,4]。比如[1,9,9]末位 9 变成 0进位前一位 9 又变成 0再进位再前一位是 1不是 9加一变成 2返回[2,0,0]。整个过程只需要改数组不需要新建。为什么当前位是 9 就把它置 0、继续往前这本质上就是在做“进位”。9 1 10个位留 0进 1 到高位。因为加的是 1所以这一位唯一能产生的进位就是 1而且进位之后当前位必为 0。所以置 0 是必然的。为什么最后return [1] [0] * n能走到循环结束说明所有的位都是 9[9]、[9,9]、[9,9,9]…… 这时候每一位都变成了 0需要在最前面补一个 1。[9]变成[0]再在头部插入 1 得到[1,0][9,9,9]变成[0,0,0]补上 1 得到[1,0,0,0]。这是唯一需要额外空间的场景。复杂度分析要会背时间复杂度最坏情况是数组全是 9需要遍历整个数组一遍O(n)最好情况是末位小于 9只访问一次O(1)。空间复杂度大多数情况是 O(1)只在全 9 时需要创建一个长度为 n1 的新数组属于 O(n)。面试时主动把这层分析讲出来非常加分。2.3 路径三语言特性与原地操作的高级写法标准解法已经够简洁了但不同语言还能玩出一些细节上的差异。这里说几个我实际写过的版本帮你对照理解语言之间的坑。C 版本class Solution { public: vectorint plusOne(vectorint digits) { int n digits.size(); for (int i n - 1; i 0; --i) { if (digits[i] 9) { digits[i]; return digits; } digits[i] 0; } digits.insert(digits.begin(), 1); return digits; } };C 的vector可以直接在头部插入insert(begin(), 1)一步到位。但要注意insert到头部的时间复杂度是 O(n)因为要搬移元素。不过这道题里你只在“全 9”这种极端情况才会调它所以无所谓。Java 版本class Solution { public int[] plusOne(int[] digits) { int n digits.length; for (int i n - 1; i 0; --i) { if (digits[i] 9) { digits[i]; return digits; } digits[i] 0; } int[] result new int[n 1]; result[0] 1; return result; } }Java 数组长度不可变这是和 C、Python 最大的区别。所以你无法“原地扩容”只能 new 一个新数组并把result[0]设为 1。新数组的其他位置默认是 0正好符合全 9 加一后低位全是 0 的规律。这里有个容易被忽略的细节Java 的int[]默认填充 0所以你不需要手动把后面 n 个位置都置 0只设第一位就够了。JavaScript 版本var plusOne function (digits) { for (let i digits.length - 1; i 0; i--) { if (digits[i] 9) { digits[i] 1; return digits; } digits[i] 0; } digits.unshift(1); return digits; };JS 的unshift可以在数组头部插入元素返回新数组长度。和 C 的insert一样unshift是 O(n) 的操作但只执行一次不影响整体复杂度。你会发现所有语言的正解逻辑一模一样变的只是“如何在头部插入 1”这个操作。这也再次说明算法思想是语言无关的但实现细节要结合语言特性来写。3. 边界情况与代码细节实录3.1 最阴险的输入全是9我在前面反复强调“全是 9”的情况因为它真的是这道题最大的坑。你把[9]加一结果不是[10]这不合法每个元素必须是单个数字而是[1,0]。这要求你的代码能处理“数组长度变化”这件事。再扩展一下[8,9,9]加一是多少手算899 1 900所以答案是[9,0,0]。这里只有第一位不是 9所以它加一变成 9返回。注意这个过程中末位的两个 9 都变成了 0然后高位从 8 变 9并没有产生新的进位。所以代码里判断digits[i] 9就加一返回正好覆盖这种场景。那[9,9,9]呢每一位都是 9遍历完整个数组之后循环自然结束这时所有位都被置为 0。注意这个时候千万不能返回digits因为[0,0,0]表示的是 0不是 1000。必须在开头补 1。我在实际刷题时见过不少人犯一个很隐蔽的错误循环写对了但全 9 情况返回的是[1, ...digits]也就是[1,0,0,0]这看起来没问题但如果你在循环里把digits改了之后直接用[1].concat(digits)实际得到的是[1,0,0,0]也正确。但有些人会把digits在循环里重置成new Array(n).fill(0)再unshift(1)这也没问题只是绕了远路。一个自查技巧写完之后用这几个用例顺一遍逻辑[1,2,3]→[1,2,4][9]→[1,0][9,9]→[1,0,0][8,9,9]→[9,0,0][0]→[1][0]可能有人会忽略但这个用例对应的是“输入的数字是 0加一得到 1”。它的存在是为了验证你的代码不会在空数组或特殊情况上报错。3.2 为什么必须从后往前处理这个问题我面试的时候问过别人也被人问过。很多人能写出从后往前遍历但问他为什么不能从前往后他就愣住了。答案其实很朴素高位的值依赖低位的进位结果。举个例子[1,9,9]如果从前往后处理先看到第一位 1你无法确定它要不要加一因为要看后面两个 9 会不会把进位一路传到最高位。你必须先处理完低位的进位才能确定高位的最终值。这就像考试时你从后往前翻试卷检查答案先确认后面的题有没有算错再回头看前面的题有没有被后面的错误影响。加法天然就是从低位往高位算的数组给你安排的存储方向最高位在左只是一个人为约定你不能被它带偏。补充一个扩展思路如果把数组换成链表力扣第 2 题“两数相加”就是链表你会发现同样是“从右往左”的进位逻辑但链表通常是从头到尾存储也就是低位在前。这时候你反而可以“从前往后”遍历了因为链表的头部正好是个位。这就是为什么我说方向感比代码本身更重要——你得先搞清楚数据结构的存储方向和进位方向的对应关系。3.3 各语言实现的差异与踩坑记录这道题的代码量很小跨语言对照特别有意思。我分别用 Java、C、Python、JavaScript 都写过总结几个容易踩的坑Java 的坑数组长度不可变全 9 时必须new int[n 1]。如果你忘了这一条试图在一个已满的数组里塞第n1个元素会直接ArrayIndexOutOfBoundsException。另外Java 的循环里返回digits是没问题的因为你是原地修改后返回引用。C 的坑如果你用digits.insert(digits.begin(), 1)要记得#include vector。如果追求性能可以改成先resize再整体后移但刷题真没必要。还有一个 C 特有的坑digits.size()返回的是size_t是无符号类型。如果你写for (int i digits.size() - 1; i 0; --i)当digits.size()为 0 时会下溢成一个巨大的正数导致死循环。不过这道题说了数组非空但最好养成用int i (int)digits.size() - 1的习惯。Python 的坑[1] [0] * n这种写法确实优雅但有些新手会写成[1].append([0] * n)这会把一个列表当作元素追加进去得到[1, [0, 0]]。注意是列表拼接append是添加元素两者天差地别。JavaScript 的坑unshift返回的是新数组的长度不是数组本身。如果你写return digits.unshift(1)返回的是一个数字而不是数组直接 WA。类似地Java 里digits[0] 1; return result;你返回的是result而不是digits一旦搞混就出问题。还有一个新手特别容易犯的错在循环里用digits.splice(i, 1, digits[i] 1)之类的方法去“删除并插入”元素。这道题完全不需要这么做因为大多数位置只是从 9 变成 0或者从某个非 9 数字变成它加一直接索引赋值就够了。4. 踩坑记录与排查技巧4.1 高频错误速查表我把这些年见过、自己也踩过的错误整理成一张表对照着查很直观错误现象错误原因正确做法大数组测试用例返回结果不对转成数字时超出语言精度范围不要整体转数字逐位处理进位[9]返回[0]或[10]没处理最高位进位、或没按单个数字拆分循环结束后在数组头部插入 1返回了数字而不是数组在 JS 里return digits.unshift(1)先unshift再return digits数组长度变了之后多了一位undefinedJS 里new Array(n 1)再手动赋值时漏掉了某些下标优先用unshift或先fill(0)再赋值C 死循环无符号类型下溢用int i (int)digits.size() - 1Java 数组越界数组长度固定没有新建数组就尝试扩容全 9 时new int[n 1]输出[1,0,0]而不是[1,0,0,0]循环里多返回了一次导致进位没传完只有遇到非 9 位才能提前返回表格里列出的前三条是最常见的。尤其是第一条“转数字丢精度”我见过太多人在评论区哀嚎“为什么我的代码输出是错的”一查全是parseInt转大数丢精度。这里再强调一次只要题目没明确说输入长度很小就不要走“整体转数字”这条路。这不仅是做题的经验写业务代码处理订单号、身份证号、银行卡号时也一样——这些字段经常超出安全整数范围你如果用Number去存数据就悄悄变了。4.2 自测用例清单与调试方法刷题不能只看样例过了就提交。这道题我建议你自测的时候把这几类输入都覆盖到普通情况[1,2,3]→[1,2,4]末位为 9[1,2,9]→[1,3,0]中间有多个 9[1,9,9]→[2,0,0]所有位都是 9[9,9,9]→[1,0,0,0]单元素[0]→[1][5]→[6][9]→[1,0]长度为 1 但值是 9[9]→[1,0]这是最容易漏的超长数组几十位主要用来验证你没走“转数字”路线调试的时候如果代码跑不对别盯着完整的大数组发呆。先用console.log或者print在每次循环里输出当前数组状态比如[1,9,9]经过三次循环后状态变化是[1,9,0]→[1,0,0]→[2,0,0]。看到这个变化过程你就能定位是在哪一步出了问题。另一个有用的调试技巧是对拍写一个暴力但一定正确的版本比如转成 Python 大整数再加一然后用随机生成的小数组反复对比。这个思路在刷更难的题时会特别有用从这道题开始养成习惯不亏。4.3 面试官的追问如果加的不是 1 而是任意数呢这道题能成为面试高频题不只是因为它简单更因为它方便做各种变形追问。我整理了几个最常见的变体追问一如果加上的不是 1而是任意一个整数k呢这个问题在力扣上对应的原题是“数组形式的整数加法”第 989 题。核心变化是进位不再只有 0 或 1你需要在循环里维护一个carry变量每次把当前位、k的对应位、以及上一次的进位一起加起来。伪代码大概是class Solution: def addToArrayForm(self, num: List[int], k: int) - List[int]: i len(num) - 1 carry 0 res [] while i 0 or k 0 or carry 0: digit carry if i 0: digit num[i] digit k % 10 k // 10 carry digit // 10 digit % 10 res.append(digit) i - 1 return res[::-1]注意这里不再用“判断当前位是不是 9”的简化写法了因为加上任意数之后进位可能大于 1比如 9 9 18进位是 1但某一位可能积累出更大的进位。所以回到最通用的carry模型。追问二如果是两个数组相加呢对应的就是力扣第 415 题“字符串相加”或第 2 题“两数相加”。思路完全一样从低位开始逐位相加维护进位处理长度不等的情况。你会发现只要把“加一”这个最简单的模型吃透这些变体都是同一个套路。追问三能优化空间复杂度吗这道题大多数情况下是原地修改空间 O(1)。全 9 的时候必须新建数组这是因为结果比输入多了一位任何算法都绕不开这个 O(n) 空间。所以正确答案是“除了全 9 分支其余都是原地修改”。你在面试时会发现把这些问题提前想明白比背 10 道题的代码有用得多。面试官其实不是在考你会不会做“加一”而是在考你能不能把“加一”背后的加法模型迁移到任何场景。5. 从第66题延伸出去的刷题路线5.1 同类“模拟进位”题推荐“加一”是最小的进位模型。如果你把这题彻底吃透了可以顺着一条线把同类题刷完形成自己的知识网络。我按递进关系整理了一份清单题目核心考点和“加一”的关系力扣 66 加一数组进位、全9边界最小原型力扣 67 二进制求和逢二进一进制变了进位逻辑不变力扣 415 字符串相加字符串处理、长度不等从数组变成字符串核心仍是进位力扣 989 数组形式的整数加法数组和整数混合相加加数从 1 变成任意大整数力扣 2 两数相加链表、高位低位存储方向数据结构变化进位逻辑复用力扣 445 两数相加 II链表逆序、栈的应用存储方向反了怎么办刷题最忌讳东一榔头西一棒槌。今天做一道数组题明天做一道链表题如果不能把它们串联起来刷 100 道和刷 10 道没本质区别。我推荐的做法是每做完一道题主动问自己“这个解法还能改造成什么题”。比如“加一”改成“加二”行不行改成“乘以二”行不行改成“二进制加一”行不行想一遍之后再去刷对应编号的题记忆会牢固得多。5.2 我的刷题方法与心得写到这里分享几个我自己刷题多年总结出来的方法尤其针对“简单题”第一简单题也要写完整复杂度分析。不要因为代码短就跳过。像这道题你要能说清楚最好情况 O(1)、最坏情况 O(n)、空间复杂度什么时候是 O(1) 什么时候是 O(n)。面试时这几乎是必问的。你现在养成习惯面试就可以条件反射。第二提交 AC 之后去看题解区的最优解和官方解。我见过不少人做“加一”用了十几行的复杂写法也能过但那是把简单问题复杂化了。看题解不是抄代码而是对比自己的思路漏掉了什么边界、能否更简洁。这道题最优雅的解法就是那几行遍历如果你能写出更简洁的版本说明你理解到位了。第三把错误的用例记在笔记本上。我不是让你把整个代码抄下来而是把踩过的坑提炼成一句话。比如“数组进位题记得全9分支”“JS 的 unshift 返回长度不是数组”“Java 数组长度不可变”。这些零散的经验汇在一起就是你自己的“刷题攻略”。第四也是最重要的如果你今天只能记住一句话请记住“边界条件想清楚再动手”。很多人在力扣上做题样例一过就提交WA 了又一脸无辜。而这道“加一”正好就是训练边界感的最佳教材。你每次处理它就等于在脑子里强化一遍“循环会不会把整个数组走完走完之后的状态是什么”这个思维习惯对后面刷任何中难题都受用。我自己每次带新人刷题都会先让他做这道题然后问他三个问题如果数组全是 9 怎么办为什么从后往前遍历能不能在常数空间内完成能把这三个问题答清楚的人后续刷题的上手速度肉眼可见地快。希望你也能把这道“简单题”真正吃透不要让它变成面试时才想起的遗憾。