教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南以「算法通关手册」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。逐位处理时个位9 1 10个位归 0向十位进 1十位9 1 10十位归 0向百位进 1百位9 1 10百位归 0向千位进 1最高位新增一位 1最终结果为[1, 0, 0, 0]。也就是说当所有位都是 9时数组长度会增加一位。这是本题最容易遗漏的边界情况。从数组结构看该思路的可行性根据仓库数组基础文档中的定义数组是一种线性表结构利用一段连续的内存空间存储一组相同类型的数据支持通过下标以 $O(1)$ 时间随机访问任意元素。本解法正是利用了数组的随机访问与按下标修改元素能力访问元素、改变元素都是 $O(1)$ 操作从低位到高位逐位处理进位。整体只需要一趟线性扫描时间复杂度为 $O(n)$。解法一前补 0 位的模拟进位法AlgoNote 题解文档给出了一个非常巧妙的实现先在数组最前面补一个 0 位这样即使最高位发生连续进位也多出一位空间可以承载最后再根据补位是否被使用来决定是否裁掉它。具体步骤数组前补 0 位digits [0] digits为可能产生的最高位进位预留位置。将个位数字加 1digits[len(digits) - 1] 1此时个位取值可能是1 ~ 10。从后向前遍历数组跳过补位下标 0如果该位数字小于 10即不为 10说明没有进位break跳出循环如果该位数字等于 10说明需要进位将该位归 0并给高一位加 1继续向前判断。收尾处理如果补位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 就能简洁地判断是否需要裁剪补位。以三个典型输入验证输入模拟过程输出[1,2,3]补位[0,1,2,3]个位变 4无进位去补位[1,2,4][4,3,2,1]补位[0,4,3,2,1]个位变 2无进位去补位[4,3,2,2][9,9,9]补位[0,9,9,9]个位变 10→0 进位十位 10→0 进位百位 10→0 进位补位变 1保留补位[1,0,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两种写法对比维度解法一补 0 位解法二直接进位边界处理用补位统一承载最高位进位循环结束后用[1] digits单独处理全 9 场景是否改变原数组长度始终多一位最后按需裁剪仅全 9 场景长度 1代码风格统一循环 标志判断命中即返回提前结束复杂度$O(n)$ 时间 / $O(1)$ 辅助空间$O(n)$ 时间 / $O(1)$ 辅助空间两种写法的时间复杂度与空间复杂度相同选哪种取决于个人风格理解进位连续传递与最高位可能新增一位这两个关键点是写出任意一种正确实现的前提。关联知识延伸1. 同一思想在仓库中的其他应用本题逐位模拟 处理进位的思路在 AlgoNote 仓库的题解中还有两个典型应用0067. 二进制求和简单同样是模拟逐位相加但基数是 2。仓库题解给出的位运算写法利用x ^ y获得无进位加法结果、(x y) 1获得进位迭代直到进位为 0与本题循环处理进位的思想一脉相承。0369. 给单链表加一中等数据结构从数组换成链表进位只能从链表末尾开始向前传递因此仓库题解使用递归从尾部回溯处理进位并在最高位仍需进位时创建新头节点——对应数组解法中补 0 位/新增一位的边界处理。2. 题目背景为什么数组能表示超长整数根据仓库数组基础文档原生 Python 中并没有严格意义上的数组通常用列表list代替其长度可动态变化、支持丰富的内置方法。本题正是利用了这一点当最高位进位导致数字位数增加时Python 列表可以灵活地通过[0] digits前插或[1] digits构建新列表从而轻松表示远超内置整数范围的超长十进制数。这类用数组/列表模拟大数运算的技巧也是后续学习高精度计算、字符串大数相加等题目的基础。3. 快速自查清单刷题或面试复盘时可以用下面几个问题自查是否真正掌握了本题个位不为 9 时能否直接digits[-1] 1并返回个位为 9、但高位存在非 9 数字时如[1,9,9]进位是否能在中途正确停止全部位都是 9 时如[9,9,9]结果长度是否比输入多一位能否准确说出两种写法各自的时间复杂度与空间复杂度总结LeetCode 0066「加一」是数组与数学结合的基础题核心是用数组模拟十进制加法从个位加 1 开始处理可能连续传递的进位并特别关注全 9 导致最高位新增一位的边界情况。AlgoNote 仓库的题解文档给出了前补 0 位 判断是否等于 10的精巧实现配合本文补充的直接进位写法、逐行推演与关联变体题读者可以完整掌握该题型的标准解法并迁移到二进制求和、链表加一等进阶题目中。完整题解可参考 docs/solutions/0001-0099/plus-one.md数组基础理论可参考 docs/01_array/01_01_array_basic.md。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析 全排列Permutations是回溯算法最经典的入门问题也是算法面试教程文档知识库AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析 本篇技术指南围绕 LeetCode 第 00教程文档知识库组合总和 II 题解AlgoNote「算法通关手册」回溯去重实战解析LeetCode 0040组合总和 II 题解AlgoNote「算法通关手册」回溯去重实战解析LeetCode 0040 本篇基于「算法通关手册」AlgoNote题库解析完整教程文档知识库上一篇RxDB RxSchema 完全指南用 JSON Schema 定义集合结构、主键、索引与加密下一篇常见问题解决trivago/prettier-plugin-sort-imports故障排除手册创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
AlgoNote 算法通关手册：LeetCode 0066「加一」数组模拟加法题解
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇技术指南以「算法通关手册」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。逐位处理时个位9 1 10个位归 0向十位进 1十位9 1 10十位归 0向百位进 1百位9 1 10百位归 0向千位进 1最高位新增一位 1最终结果为[1, 0, 0, 0]。也就是说当所有位都是 9时数组长度会增加一位。这是本题最容易遗漏的边界情况。从数组结构看该思路的可行性根据仓库数组基础文档中的定义数组是一种线性表结构利用一段连续的内存空间存储一组相同类型的数据支持通过下标以 $O(1)$ 时间随机访问任意元素。本解法正是利用了数组的随机访问与按下标修改元素能力访问元素、改变元素都是 $O(1)$ 操作从低位到高位逐位处理进位。整体只需要一趟线性扫描时间复杂度为 $O(n)$。解法一前补 0 位的模拟进位法AlgoNote 题解文档给出了一个非常巧妙的实现先在数组最前面补一个 0 位这样即使最高位发生连续进位也多出一位空间可以承载最后再根据补位是否被使用来决定是否裁掉它。具体步骤数组前补 0 位digits [0] digits为可能产生的最高位进位预留位置。将个位数字加 1digits[len(digits) - 1] 1此时个位取值可能是1 ~ 10。从后向前遍历数组跳过补位下标 0如果该位数字小于 10即不为 10说明没有进位break跳出循环如果该位数字等于 10说明需要进位将该位归 0并给高一位加 1继续向前判断。收尾处理如果补位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 就能简洁地判断是否需要裁剪补位。以三个典型输入验证输入模拟过程输出[1,2,3]补位[0,1,2,3]个位变 4无进位去补位[1,2,4][4,3,2,1]补位[0,4,3,2,1]个位变 2无进位去补位[4,3,2,2][9,9,9]补位[0,9,9,9]个位变 10→0 进位十位 10→0 进位百位 10→0 进位补位变 1保留补位[1,0,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两种写法对比维度解法一补 0 位解法二直接进位边界处理用补位统一承载最高位进位循环结束后用[1] digits单独处理全 9 场景是否改变原数组长度始终多一位最后按需裁剪仅全 9 场景长度 1代码风格统一循环 标志判断命中即返回提前结束复杂度$O(n)$ 时间 / $O(1)$ 辅助空间$O(n)$ 时间 / $O(1)$ 辅助空间两种写法的时间复杂度与空间复杂度相同选哪种取决于个人风格理解进位连续传递与最高位可能新增一位这两个关键点是写出任意一种正确实现的前提。关联知识延伸1. 同一思想在仓库中的其他应用本题逐位模拟 处理进位的思路在 AlgoNote 仓库的题解中还有两个典型应用0067. 二进制求和简单同样是模拟逐位相加但基数是 2。仓库题解给出的位运算写法利用x ^ y获得无进位加法结果、(x y) 1获得进位迭代直到进位为 0与本题循环处理进位的思想一脉相承。0369. 给单链表加一中等数据结构从数组换成链表进位只能从链表末尾开始向前传递因此仓库题解使用递归从尾部回溯处理进位并在最高位仍需进位时创建新头节点——对应数组解法中补 0 位/新增一位的边界处理。2. 题目背景为什么数组能表示超长整数根据仓库数组基础文档原生 Python 中并没有严格意义上的数组通常用列表list代替其长度可动态变化、支持丰富的内置方法。本题正是利用了这一点当最高位进位导致数字位数增加时Python 列表可以灵活地通过[0] digits前插或[1] digits构建新列表从而轻松表示远超内置整数范围的超长十进制数。这类用数组/列表模拟大数运算的技巧也是后续学习高精度计算、字符串大数相加等题目的基础。3. 快速自查清单刷题或面试复盘时可以用下面几个问题自查是否真正掌握了本题个位不为 9 时能否直接digits[-1] 1并返回个位为 9、但高位存在非 9 数字时如[1,9,9]进位是否能在中途正确停止全部位都是 9 时如[9,9,9]结果长度是否比输入多一位能否准确说出两种写法各自的时间复杂度与空间复杂度总结LeetCode 0066「加一」是数组与数学结合的基础题核心是用数组模拟十进制加法从个位加 1 开始处理可能连续传递的进位并特别关注全 9 导致最高位新增一位的边界情况。AlgoNote 仓库的题解文档给出了前补 0 位 判断是否等于 10的精巧实现配合本文补充的直接进位写法、逐行推演与关联变体题读者可以完整掌握该题型的标准解法并迁移到二进制求和、链表加一等进阶题目中。完整题解可参考 docs/solutions/0001-0099/plus-one.md数组基础理论可参考 docs/01_array/01_01_array_basic.md。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析 全排列Permutations是回溯算法最经典的入门问题也是算法面试教程文档知识库AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析AlgoNote 算法通关手册LeetCode 0036 有效的数独Valid Sudoku哈希表解法全解析 本篇技术指南围绕 LeetCode 第 00教程文档知识库组合总和 II 题解AlgoNote「算法通关手册」回溯去重实战解析LeetCode 0040组合总和 II 题解AlgoNote「算法通关手册」回溯去重实战解析LeetCode 0040 本篇基于「算法通关手册」AlgoNote题库解析完整教程文档知识库上一篇RxDB RxSchema 完全指南用 JSON Schema 定义集合结构、主键、索引与加密下一篇常见问题解决trivago/prettier-plugin-sort-imports故障排除手册创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
