企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南以「算法通关手册」（AlgoNote）仓库中 LeetCode 0066「加一」（Plus One）的题解文档为核心，完整讲解基于数组模拟加法运算的思路、可运行的 Python 代码与复杂度分析，并结合仓库源码补充数组底层原理、进位细节与同类变体题（如链表加一）的延伸解法，帮助读者掌握大数加一这类"数组模拟竖式运算"题型的通用套路。

题目信息与核心考点

• 题目编号：0066. 加一（Plus One）
• 标签：数组、数学
• 难度：简单
• 题目链接：0066. 加一 - 力扣

在 AlgoNote 仓库中，本题被归入数组基础题型，出现在题解总览列表与分类题目列表中，同时也是数组基础章节推荐的练习题目之一。

题目大意

给定一个非负整数数组，数组中每一位对应这个整数的一位数字（按十进制从高位到低位排列）。要求：计算这个整数加 1之后的结果，仍然以数组形式返回。

题目约束条件：

• $1 \le digits.length \le 100$，即数组最长可达 100 位。
• $0 \le digits[i] \le 9$，即每一位都是十进制数字。
• 数组本身不包含前导零（除 0 本身之外）。

示例

• 示例 1：

输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123，加 1 之后为 124。

• 示例 2：

输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321，加 1 之后为 4322。

由于数组长度上限为 100，远超常规语言中 64 位整数（约 19 位十进制数）的表示范围，因此本题不能把数组先转成整数再加 1 再转回数组，必须直接在数组上模拟十进制加法运算——这正是本题的核心考点。

思路分析：用数组模拟加法运算

AlgoNote 题解文档给出的思路是「模拟」：把整个数组看成一个整数，对"个位"（即数组最后一个元素）加 1，问题的实质是利用数组模拟加法运算（竖式加法）。

模拟竖式加法时需要考虑的关键分情况：

• 如果个位数不为 9，直接把个位数加 1 即可，不会产生进位。
• 如果个位数为 9，加 1 后变成 10，需要向高一位进位，并且要把当前位归 0；进位后高一位可能又是 9，因此进位可能连续传递。

为什么必须处理进位

以[9, 9, 9]为例，它表示数字 999，加 1 后应为 1000。逐位处理时：

1. 个位9 + 1 = 10，个位归 0，向十位进 1；
2. 十位9 + 1 = 10，十位归 0，向百位进 1；
3. 百位9 + 1 = 10，百位归 0，向千位进 1；
4. 最高位新增一位 1，最终结果为[1, 0, 0, 0]。

也就是说，当所有位都是 9时，数组长度会增加一位。这是本题最容易遗漏的边界情况。

从数组结构看该思路的可行性

根据仓库数组基础文档中的定义，数组是一种线性表结构，利用一段连续的内存空间存储一组相同类型的数据，支持通过下标以 $O(1)$ 时间随机访问任意元素。本解法正是利用了数组的随机访问与按下标修改元素能力（访问元素、改变元素都是 $O(1)$ 操作），从低位到高位逐位处理进位。整体只需要一趟线性扫描，时间复杂度为 $O(n)$。

解法一：前补 0 位的模拟进位法

AlgoNote 题解文档给出了一个非常巧妙的实现：先在数组最前面补一个 0 位，这样即使最高位发生连续进位，也多出一位空间可以承载，最后再根据补位是否被使用来决定是否裁掉它。

具体步骤

1. 数组前补 0 位：digits = [0] + digits，为可能产生的最高位进位预留位置。
2. 将个位数字加 1：digits[len(digits) - 1] += 1，此时个位取值可能是1 ~ 10。
3. 从后向前遍历数组（跳过补位下标 0）：
   • 如果该位数字小于 10（即不为 10），说明没有进位，break跳出循环；
   • 如果该位数字等于 10，说明需要进位：将该位归 0，并给高一位加 1，继续向前判断。
4. 收尾处理：如果补位digits[0]仍为 0，说明最高位没有产生进位，返回digits[1:]（去掉补位）；否则说明最高位进位成功（如 999 + 1 的情形），直接返回整个数组。

可运行代码

from typing import List class Solution: def plusOne(self, digits: List[int]) -> List[int]: # 1. 数组前补 0 位，为最高位进位预留空间 digits = [0] + digits # 2. 个位数字加 1 digits[len(digits) - 1] += 1 # 3. 从后向前处理进位 for i in range(len(digits) - 1, 0, -1): if digits[i] != 10: break else: digits[i] = 0 digits[i - 1] += 1 # 4. 判断补位是否被使用 if digits[0] == 0: return digits[1:] else: return digits

注：原题解代码位于 docs/solutions/0001-0099/plus-one.md，此处补充了List的类型导入与注释，使其可直接在 LeetCode 环境或本地 Python 3 环境中运行。

逐行推演：为什么这个写法很巧妙

核心在于用"补 0 位 + 判断是否等于 10"统一处理"无进位"与"有进位"两种情况：

• 个位加 1 后，每一位的可能取值只有两种：不是 10（说明该位最终结果 < 10，无需进位），就是 10（需要进位）。
• 从右向左扫描时，只要遇到"不等于 10"的位就立刻break，因为高位不会再受影响。
• 补位digits[0]只可能被进位影响变成 1（全 9 场景）或保持 0（其他场景），因此最后通过digits[0]是否为 0 就能简洁地判断是否需要裁剪补位。

以三个典型输入验证：

复杂度分析

• 时间复杂度：$O(n)$。一重循环从后向前遍历数组，最多遍历 $n$ 个元素；实际在遇到第一个非 10 的位时即可提前break，平均情况下更快。
• 空间复杂度：$O(1)$（不计返回结果）。虽然digits = [0] + digits会创建一份新的列表，但从算法的辅助空间角度看，我们是在原数组基础上原地修改进位，没有引入随 $n$ 增长的额外存储。

解法二：从后向前的直接进位法（扩展思路）

除了题解文档给出的"补 0 位"写法，还可以采用不补位、从后向前直接进位的写法，这是面试中常见的等价实现，逻辑更直白：

from typing import List 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: # 当前位加 1 后不会进位，直接结束 digits[i] += 1 return digits # 当前位为 9，加 1 后归 0，进位继续向前传递 digits[i] = 0 # 循环结束说明所有位都是 9，如 999 -> 1000 return [1] + digits

两种写法对比：

两种写法的时间复杂度与空间复杂度相同，选哪种取决于个人风格；理解"进位连续传递"与"最高位可能新增一位"这两个关键点，是写出任意一种正确实现的前提。

关联知识延伸

1. 同一思想在仓库中的其他应用

本题"逐位模拟 + 处理进位"的思路，在 AlgoNote 仓库的题解中还有两个典型应用：

• 0067. 二进制求和（简单）：同样是模拟逐位相加，但基数是 2。仓库题解给出的位运算写法利用x ^ y获得无进位加法结果、(x & y) << 1获得进位，迭代直到进位为 0，与本题"循环处理进位"的思想一脉相承。
• 0369. 给单链表加一（中等）：数据结构从数组换成链表，进位只能从链表末尾开始向前传递，因此仓库题解使用递归从尾部回溯处理进位，并在最高位仍需进位时创建新头节点——对应数组解法中"补 0 位/新增一位"的边界处理。

2. 题目背景：为什么数组能表示超长整数

根据仓库数组基础文档，原生 Python 中并没有严格意义上的"数组"，通常用列表（list）代替，其长度可动态变化、支持丰富的内置方法。本题正是利用了这一点：当最高位进位导致数字位数增加时，Python 列表可以灵活地通过[0] + digits前插或[1] + digits构建新列表，从而轻松表示远超内置整数范围的超长十进制数。这类"用数组/列表模拟大数运算"的技巧，也是后续学习高精度计算、字符串大数相加等题目的基础。

3. 快速自查清单

刷题或面试复盘时，可以用下面几个问题自查是否真正掌握了本题：

1. 个位不为 9 时，能否直接digits[-1] += 1并返回？
2. 个位为 9、但高位存在非 9 数字时（如[1,9,9]），进位是否能在中途正确停止？
3. 全部位都是 9 时（如[9,9,9]），结果长度是否比输入多一位？
4. 能否准确说出两种写法各自的时间复杂度与空间复杂度？

总结

LeetCode 0066「加一」是数组与数学结合的基础题，核心是用数组模拟十进制加法：从个位加 1 开始，处理可能连续传递的进位，并特别关注"全 9 导致最高位新增一位"的边界情况。AlgoNote 仓库的题解文档给出了"前补 0 位 + 判断是否等于 10"的精巧实现，配合本文补充的直接进位写法、逐行推演与关联变体题，读者可以完整掌握该题型的标准解法，并迁移到二进制求和、链表加一等进阶题目中。完整题解可参考 docs/solutions/0001-0099/plus-one.md，数组基础理论可参考 docs/01_array/01_01_array_basic.md。

• 教程
• 文档
• 知识库