文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载本篇是 algorithm-base 仓库 数组篇 下的经典题目精讲围绕 LeetCode 66「加一Plus One」展开给定一个用数组表示的非负整数要求将其加一并以数组形式返回。读完本文你将掌握基于「倒序遍历 % 10取余」的单次遍历解法如何用同一段逻辑覆盖“无进位、有进位、全 9 进位”三种情况并理解该解法在 Java、Python、C、Swift、Go 五种语言下的等价实现以及时间、空间复杂度的准确分析。题目描述给定一个由整数组成的非空数组所表示的非负整数在该数的基础上加一。最高位数字存放在数组的首位数组中每个元素只存储单个数字你可以假设除了整数0之外这个整数不会以零开头。示例 1输入digits [1,2,3]输出[1,2,4]解释输入数组表示数字 123。示例 2输入digits [4,3,2,1]输出[4,3,2,2]解释输入数组表示数字 4321。示例 3输入digits [0]输出[1]题目解析加一只有三种情况我们思考一下加一的情况一共有几种是不是有以下三种情况特征例子结果第一种末位不是 9加一后不发生进位[1,2,3] → 123 1 124[1,2,4]第二种末位及若干低位是 9进位传递到中间某一位后停止[1,9,9] → 199 1 200[2,0,0]第三种所有位都是 9进位贯穿整个数组需要扩展一位[9,9,9] → 999 1 1000[1,0,0,0]那么我们应该根据什么来判断当前属于第几种情况呢答案是根据当前位「余 10」的结果来判断。对任意一位执行(digits[i] 1) % 10若该位是0~8加一取余后得到digits[i] 1结果不为 0说明进位到此为止属于第一、二种情况直接返回即可若该位是9加一取余后得到0说明产生了进位需要继续向左处理更高位若整个循环走完每一位都变成了 0说明属于第三种“全 9”情况此时只需申请一个长度len 1的数组、把首位置为1即可——因为新数组初始化后每一位天然都是 0。这个思路非常直观大家直接看代码吧很容易理解。核心解法数组遍历倒序 取余Java Codeclass Solution { public int[] plusOne(int[] digits) { //获取长度 int len digits.length; for (int i len-1; i 0; i--) { digits[i] (digits[i] 1) % 10; //第一种和第二种情况如果此时某一位不为 0 则直接返回即可。 if (digits[i] ! 0) { return digits; } } //第三种情况因为数组初始化每一位都为0我们只需将首位设为1即可 int[] arr new int[len1]; arr[0] 1; return arr; } }Python Codefrom typing import List class Solution: def plusOne(self, digits: List[int])-List[int]: # 获取长度 leng len(digits) for i in range(leng - 1, -1, -1): digits[i] (digits[i] 1) % 10 # 第一种和第二种情况如果此时某一位不为 0 则直接返回即可。 if digits[i] ! 0: return digits # 第三种情况因为数组初始化每一位都为0我们只需将首位设为1即可 arr [0] * (leng 1) arr[0] 1 return arrC Codeclass Solution { public: vectorint plusOne(vectorint digits) { for(int i digits.size() - 1; i 0; --i){ digits[i] (digits[i] 1)%10; if(digits[i]) return digits; } for(int x: digits) x 0; digits.emplace_back(1); reverse(digits.begin(), digits.end()); return digits; } };C 版本对“全 9”情况采用了不同的落点循环结束后数组所有位已全部为 0for清零循环在这里是防御性写法保证逻辑自洽随后emplace_back(1)在末尾追加1再reverse翻转使1回到首位得到[1, 0, 0, ...]。整个过程复用了原vector无需申请新容器。Swift Codeclass Solution { func plusOne(_ digits: [Int]) - [Int] { let count digits.count var digits digits for i in stride(from: count - 1, through: 0, by: -1) { digits[i] (digits[i] 1) % 10 if digits[i] ! 0 { return digits } } var arr: [Int] Array.init(repeating: 0, count: count 1) arr[0] 1 return arr } }Go Codefunc plusOne(digits []int) []int { l : len(digits) for i : l - 1; i 0; i-- { digits[i] (digits[i] 1) % 10 if digits[i] ! 0 { return digits } } digits append([]int{1}, digits...) return digits }Go 版本在“全 9”时使用append([]int{1}, digits...)把1拼到原切片头部生成[1, 0, 0, ...]语义上同样等价。复杂度与边界分析时间复杂度O(n)其中 n 为数组长度。最坏情况下如[9,9,...,9]需要从末位遍历到首位但仍是一次线性扫描空间复杂度O(1)除全 9 分支。第一、二种情况在原数组上就地修改并返回不申请额外空间第三种情况需要申请长度为len 1的新数组此时空间开销为 O(n)。C 版本通过复用vector做到了全场景 O(1) 额外空间边界 1单个元素。[0] → [1]属于第一种情况[9] → [1,0]属于第三种情况代码都能正确处理边界 2数字不以 0 开头。题目保证除0本身外不以零开头因此数组首位一定是1~9我们无需额外判断前导零取余技巧的本质(x 1) % 10对x ∈ [0,9]而言等价于“不进位则自增、为 9 则归零”恰好把“是否产生进位”的信息编码进了结果是否为0从而让三种情况共用同一套循环逻辑。在 algorithm-base 仓库中的定位与延伸本讲所在的 animation-simulation/数组篇 是 algorithm-base 仓库“数组篇”知识体系的一部分仓库 README.md 将该题归入「 数组篇」的动画模拟/绘图描述系列与 两数之和、移除元素、缺失的第一个正数、颜色分类 等题并列适合按数组专题顺序刷读。刷题过程中可搭配仓库的 Leetcode 常用类和函数 了解数组相关的length注意 Java 中数组长度属性后不加括号、Arrays.fill()、Arrays.sort()等高频工具加深对数组操作的理解。如果你想围绕“数字的逐位运算与进位”做延伸训练仓库中还有几个强相关的姊妹题链表求和面试题 02.05同样是逐位加法与进位但载体换成了链表且数位是反向存放的进位处理的思路与本篇高度互通缺失的第一个正数LeetCode 41同样需要在数组上进行原地重排与位置映射锻炼“数组即哈希表”的思维数组中重复的数字剑指 Offer 03利用数组下标与值的对应关系做原地判断属于同一类数组技巧的延伸。总结一句LeetCode 66 这道题虽然代码极短但“倒序遍历 % 10判断进位 全 9 兜底”的套路是数组题目里非常经典的一种模式吃透它你在处理任何“大数逐位运算”类问题时都会更有底气。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode 66. Plus One加一题解数组反向遍历模拟加法与进位传播的完整解析LeetCode 66. Plus One加一题解数组反向遍历模拟加法与进位传播的完整解析 本文以 leetcode 仓库中的 problems/66.p文档教程知识库LeetCode 66. 加一Plus One题解反向遍历与进位传播的多语言实现LeetCode 66. 加一Plus One题解反向遍历与进位传播的多语言实现 本篇题解以 problems/66.plus one.md https:文档教程知识库LeetCode-Go 题解 66Plus One 的 Go 实现——数组逐位进位模拟与全 9 进位边界处理LeetCode Go 题解 66Plus One 的 Go 实现——数组逐位进位模拟与全 9 进位边界处理 本文以 LeetCode Go 仓库中第 66示例工程上一篇探索ZenML一款现代、可扩展的机器学习操作系统下一篇Standalone Migrations如何在非Rails项目中轻松管理数据库迁移创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
