C++实现LeetCode(66.加一运算)

前言LeetCode 第 66 题「加一」的要求是给定一个由整数组成的非空数组数组按最高位在前的顺序表示一个非负整数把这个整数加一返回结果数组。例如[1, 2, 3]表示 123加一后是[1, 2, 4][9, 9]表示 99加一后是[1, 0, 0]。这道题常被当作「数组遍历」的入门题但它真正考的是进位模型什么时候可以直接加一并返回什么时候必须把当前位清零继续向左什么时候需要在最前面补一位。三个分支对应三种情况漏掉任何一个都会在特定输入上出错。初学者最容易犯的错误是把数组转成一个整数再1然后拆回数组。这个做法在数组很短时「看起来能用」但数组长度可能达到一百位远超int、long long甚至__int128的范围转换过程本身就是溢出。另一类错误是循环变量用无符号类型写成for (std::size_t i digits.size() - 1; i 0; --i)当i减到 0 之后再自减会回绕成极大值循环永远不会结束。本文从进位模型讲起给出原地修改与不修改输入两种写法再延伸到「加任意整数」和「字符串大数相加」最后列出常见错误。所有复杂度都按标准语义分析不涉及任何运行时间测量。一、题意拆解题目有三个隐含约定读题时要确认非空数组至少有一个元素所以不必处理空数组。无前导零除了数字 0 本身表示为[0]其它情况最高位不为 0。最高位在前digits[0]是最高位digits[n-1]是个位。加一运算只影响从个位开始的一段连续 9。具体来说如果个位小于 9直接加一其余位不变立刻返回如果个位是 9加一后变成 10本位记 0进位 1 传给前一位如果连续一段可能一直到最高位都是 9它们全部变 0并在最前面插入一个 1。这个观察就是全部算法从右往左扫描遇到第一个小于 9 的位就加一并返回扫描完整个数组都没返回说明全是 9在最前面插入 1。二、为什么不能转成整数假设数组长度是 100每一位都是 9。这个数约等于 10 的 100 次方而 64 位无符号整数的上限约是 1.8×10 的 19 次方。用long long或unsigned long long都装不下转换时会发生截断或溢出。即便数组很短转换也有其它问题需要额外的乘加循环复杂度没有变好有符号整数溢出是未定义行为不能依赖「溢出后回绕」这种假设。逐位处理没有这些负担而且天然支持任意长度。方案时间额外空间长度上限正确性风险转成long long再加一O(n)O(n)约 19 位长数组必然溢出逐位进位原地O(n)O(1)仅受内存限制无逐位进位新数组O(n)O(n)仅受内存限制无三、原地修改的写法// 适用于 C17#include vectorclass Solution {public:std::vectorint plusOne(std::vectorint digits) {// 从个位开始向左扫描for (int i static_castint(digits.size()) - 1; i 0; --i) {if (digits[i] 9) {digits[i]; // 不需要进位直接加一并结束return digits;}digits[i] 0; // 这一位是 9加一后变 0继续向左进位}// 走到这里说明所有位都是 9需要在最高位前补 1digits.insert(digits.begin(), 1);return digits;}};几个细节值得说明循环变量用int而不是std::size_t。digits.size()是无符号的size_t减一之后如果数组非空没问题但循环条件i 0对无符号类型永远成立会死循环。题目保证数组非空所以static_castint(digits.size()) - 1不会得到负数前提是长度不超过int的上限实际题目远达不到。return digits;返回的是std::vectorint的副本。函数签名返回类型是值类型这里会触发一次拷贝由于返回值优化RVO和移动语义编译器通常会消除或转为移动但语义上它是一次返回。全 9 的情况用insert在头部插入。std::vector::insert在头部插入的时间复杂度是 O(n)因为要移动所有已有元素。整个算法最坏情况下也是 O(n)所以总复杂度仍是 O(n)。如果不想修改输入可以传值// 适用于 C17#include vectorstd::vectorint plusOneCopy(std::vectorint digits) {for (int i static_castint(digits.size()) - 1; i 0; --i) {if (digits[i] 9) {digits[i];return digits;}digits[i] 0;}digits.insert(digits.begin(), 1);return digits;}参数按值传递函数内部操作的是副本调用者的数组不受影响。代价是一次 O(n) 的拷贝但代码更安全适合「入参不可变」的接口约定。四、用反向迭代器改写如果不喜欢下标与符号的纠缠可以用反向迭代器// 适用于 C17#include vectorstd::vectorint plusOneIter(std::vectorint digits) {for (auto it digits.rbegin(); it ! digits.rend(); it) {if (*it 9) {(*it);return digits;}*it 0;}digits.insert(digits.begin(), 1);return digits;}rbegin()指向最后一个元素rend()指向第一个元素之前的位置。反向迭代器的是向左移动正好符合「从个位向高位」的扫描方向也不会出现无符号下溢。这段代码的可读性通常比下标版本更好。五、扩展到「加任意整数」把「加一」推广成「加 k」进位就不再是 0 或 1而是一个可能大于 1 的进位值// 适用于 C17#include vectorstd::vectorint addInt(std::vectorint digits, int k) {int carry k;for (int i static_castint(digits.size()) - 1; i 0 carry 0; --i) {const int sum digits[i] carry;digits[i] sum % 10;carry sum / 10;}while (carry 0) {digits.insert(digits.begin(), carry % 10);carry / 10;}return digits;}这里有两个循环第一个处理数组内部的进位第二个处理「进位超出最高位」的情况。比如[9, 9]加 1第一个循环结束后digits是[0, 0]、carry是 1第二个循环把 1 插到最前面。如果 k 很大比如 12345第二个循环会依次插入多位注意插入顺序每次插入的是carry % 10然后carry / 10最终得到的是正确的高位序列。这个版本假设 k 非负。如果要支持负数需要先比较被减数与减数的大小再决定做加法还是减法复杂度会上升不少属于另一类「大数运算」的范畴。六、复杂度分析操作时间复杂度说明从右往左扫描O(n)最多检查 n 位头部插入 1O(n)需要移动所有元素整体O(n)最坏情况全 9扫描加插入额外空间O(1)原地版本只用几个标量最坏情况是数组全为 9扫描 n 位全部置 0再插入一位并移动 n 个元素总共约 2n 次操作仍是 O(n)。最好情况是个位小于 9只做一次比较和一次自增O(1)。常见坑点1. 把数组转成整数再计算❌long long v 0; for (int d : digits) v v * 10 d; v 1;再拆回数组 ✅ 逐位处理进位数组长度可以到一百位任何内置整数类型都装不下。转换过程中的乘法本身也会溢出而有符号溢出是未定义行为。2. 无符号循环变量导致死循环❌for (std::size_t i digits.size() - 1; i 0; --i)✅for (int i static_castint(digits.size()) - 1; i 0; --i)或反向迭代器std::size_t是无符号类型减到 0 之后再自减会回绕成一个极大值i 0永远为真。这类错误在数组为空时还会直接在size() - 1处下溢。3. 忘了全 9 需要在头部补位❌ 循环里把 9 置 0 后直接return digits;✅ 循环结束后执行digits.insert(digits.begin(), 1);[9, 9]加一的结果是[1, 0, 0]长度增加了一位。如果只在原长度内处理会得到[0, 0]既少了最高位数值也完全错了。4. 加一之后没有立即返回❌if (digits[i] 9) { digits[i]; }然后继续循环 ✅if (digits[i] 9) { digits[i]; return digits; }不需要进位的位一旦加一左边的所有位都不应该再变。继续循环会把前面的位也加一结果偏大。5. 认为头部插入是 O(1)❌ 「insert(begin(), 1)只加一个元素所以是常数时间」 ✅ 头部插入需要把已有元素整体后移复杂度是 O(n)std::vector是连续存储任何非尾部插入都会移动元素并且会使所有迭代器失效。分析复杂度时不能只看「插入了几个元素」。6. 返回局部数组的引用❌std::vectorint plusOne(std::vectorint digits) { ... return digits; }用在返回临时对象的场合 ✅ 返回std::vectorint值类型返回引用本身在参数是左值时没问题但一旦传入临时对象或函数内部构造的数组引用就会悬垂。返回值的写法更通用编译器也会用 RVO 或移动避免多余拷贝。7. 处理前导零时误删合法位❌ 结果里出现[0, 0]就断言「有前导零需要去掉第一个 0」 ✅ 只有题目明确要求「输出去除前导零」时才处理且要保留单独的一个 0本题的输入保证无前导零输出也不应该出现前导零除非结果就是 0但加一之后不可能是 0。擅自删除元素会改变数值。8. 修改了入参却对外声称未修改❌ 文档写「不改变输入」实现却直接对digits自增 ✅ 需要只读语义时按值传参或在函数内先复制一份接口约定与实现不一致调用方可能复用原数组做后续计算得到的是被改过的数据。这类问题不会立刻报错属于最难排查的一类缺陷。总结要点结论核心模型从个位向左找第一个小于 9 的位加一即止全 9 处理全部置 0头部插入 1长度加一时间复杂度O(n)最坏情况扫描加头部插入空间复杂度原地版 O(1)复制版 O(n)循环变量用有符号下标或反向迭代器避免无符号下溢整数转换禁止长数组必然溢出这道题的代码只有十几行但它把三个基本功串在了一起边界情况全 9、类型细节无符号下溢、复杂度直觉头部插入不是常数时间。把「加一」的进位模型想清楚再推广到「加任意整数」和「两个大数相加」就是一套完整的十进制大数运算框架。写这类题时先在纸上把[9]、[9, 9]、[1, 9, 9]、[8]四个例子走一遍比直接敲代码更有效率。