LeetCode 66. 加一：两种高效解法详解

在LeetCode的基础算法题中「加一」是一道经典的数组操作题看似简单却藏着对边界场景的考量尤其适合新手入门数组遍历和边界处理。这道题的核心是模拟大整数加1的过程——因为题目中的整数可能极大无法直接转为Number类型计算只能通过数组逐位操作来实现今天就来详细拆解两种高效解法帮大家吃透这道题的思路和细节。一、题目回顾清晰理解需求题目给出一个表示大整数的整数数组 digits满足以下条件digits[i] 是整数的第 i 位数字按「从左到右、从最高位到最低位」排列比如 digits [1,2,3] 表示整数 123这个大整数不包含任何前导 0即 digits[0] 不会是 0除非数组长度为1且 digits [0]。要求将这个大整数加 1返回结果的数字数组比如 [1,2,3] 加1后返回 [1,2,4][9,9,9] 加1后返回 [1,0,0,0]。核心难点处理「末尾全是9」的边界情况如 [9]→[1,0]、[9,9]→[1,0,0]避免直接操作导致的逻辑漏洞。二、解法一逆序遍历找非9元素清晰易懂逻辑直观1. 思路分析大整数加1本质是从「最低位」数组最后一位开始计算只有当当前位是9时加1才会产生进位否则直接加1即可后续位无需修改全部置0。基于这个逻辑我们可以分两步走逆序遍历数组找到第一个不为9的元素这个元素就是加1的位置其后面的所有元素都是9需要置为0处理边界情况如果遍历完所有元素都没有找到非9元素即数组全是9说明加1后会新增一位在数组开头插入1即可。2. 完整TS代码functionplusOne_1(digits:number[]):number[]{// 逆序遍历找到第一个不为9的元素索引letindex-1;for(letidigits.length-1;i0;i--){if(digits[i]9){continue;// 是9继续向前找}else{indexi;// 找到非9元素记录索引并退出循环break;}}// 将找到的非9元素后面的所有元素置为0都是9加1后需归零for(letiindex1;idigits.length;i){digits[i]0;}// 处理边界全是9的情况index仍为-1否则给非9元素加1if(index-1){digits.unshift(1);// 新增最高位1}else{digits[index];}returndigits;};3. 代码细节拆解index初始值为-1用于标记「是否找到非9元素」若遍历结束仍为-1说明数组全是9第一次逆序遍历只找第一个非9元素找到后立即退出避免多余遍历时间复杂度O(n)最坏情况遍历整个数组第二次遍历仅将非9元素后面的元素置0无需遍历整个数组进一步优化效率unshift(1)在数组开头插入1对应「全9加1」的场景如 [9,9] → [1,0,0]。三、解法二逆序遍历直接处理更简洁减少一次遍历1. 思路优化解法一的核心逻辑是「先找非9元素再置0、加1」而解法二将这两个步骤合并在逆序遍历的过程中直接处理逆序遍历数组遇到非9元素时直接加1然后将其后面的所有元素置为0直接返回数组因为后续元素无需再处理如果遍历完所有元素都没有遇到非9元素全9则创建一个长度为n1的新数组默认填充0将第一个元素设为1相当于在原数组前加1返回新数组。这种解法的优势的是「提前返回」减少不必要的遍历代码更简洁逻辑更紧凑。2. 完整TS代码functionplusOne_2(digits:number[]):number[]{constndigits.length;for(letin-1;i0;i--){if(digits[i]!9){digits[i];// 非9元素直接加1// 将后面的所有9置为0for(letji1;jn;j){digits[j]0;}returndigits;// 处理完毕直接返回}}// 走到这里说明数组全是9constansnewArray(n1).fill(0);ans[0]1;returnans;};3. 代码细节拆解提前返回只要找到非9元素处理完当前位加1和后续位置0后直接返回数组无需继续遍历效率更高新数组创建全9场景下不修改原数组直接创建新数组长度n1避免unshift操作unshift会改变原数组且时间复杂度为O(n)但此处两种方式效率差异不大边界处理更简洁无需额外标记index通过「遍历是否结束」判断是否全为9逻辑更紧凑。四、两种解法对比选择适合自己的方式对比维度解法一解法二时间复杂度O(n)最坏两次遍历实际效率接近O(n)O(n)最坏一次遍历提前返回更高效空间复杂度O(1)除了原数组无额外空间unshift修改原数组O(n)全9场景下创建新数组否则O(1)代码复杂度稍繁琐逻辑分步清晰适合新手理解更简洁逻辑紧凑适合熟练后使用核心优势步骤明确边界处理直观易调试提前返回减少遍历代码更优雅五、常见测试用例验证解法正确性无论是哪种解法都需要覆盖以下几种核心测试用例确保逻辑无漏洞普通情况无进位digits [1,2,3] → 输出 [1,2,4]末尾有进位非全9digits [1,2,9] → 输出 [1,3,0]全9情况边界digits [9,9,9] → 输出 [1,0,0,0]单个元素边界digits [9] → 输出 [1,0]digits [0] → 输出 [1]。大家可以将这几个用例代入两种解法验证代码是否能正确运行也可以自己动手调试感受两种思路的差异。六、总结与思考LeetCode 66.加一虽然是一道简单题但核心考察的是「边界处理」和「数组遍历技巧」——很多新手容易忽略「全9加1」的场景导致代码报错。通过这两种解法我们可以学到逆序遍历是处理「从低位到高位」计算的常用技巧如加法、减法的模拟边界场景的提前判断的重要性能避免不必要的计算提升代码效率同一问题可以有不同的实现思路既要追求代码简洁也要保证逻辑清晰适合自己的才是最好的。