Vue.js

Appearance

On this page

实战：加一 ​

这是一道模拟题，考察的是进位处理的逻辑。

看似简单，但有一个容易忽略的边界情况。

题目描述 ​

LeetCode 66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

示例 1：

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

示例 2：

输入：digits = [9, 9, 9]
输出：[1, 0, 0, 0]
解释：输入数组表示数字 999，加一后为 1000

题目分析 ​

模拟我们手算加法的过程：

  1. 从最低位（数组末尾）开始
  2. 加一
  3. 如果有进位，继续处理前一位

关键问题：什么时候会产生进位？

当这一位是 9 时，加一变成 10，需要进位。

解法：模拟进位 ​

javascript
function plusOne(digits) {
    const n = digits.length;
    
    // 从末尾开始处理
    for (let i = n - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            // 不需要进位，直接加一返回
            digits[i]++;
            return digits;
        }
        // 当前位是 9，变成 0，继续处理前一位
        digits[i] = 0;
    }
    
    // 所有位都是 9，需要在最前面加 1
    // 例如 [9, 9, 9] -> [1, 0, 0, 0]
    return [1, ...digits];
}

代码很简洁。核心逻辑是：

  1. 不是 9：直接加一，结束
  2. 是 9：变成 0，处理前一位（相当于进位）
  3. 全是 9：所有位都变成 0，在最前面加个 1

执行过程 ​

Case 1：[1, 2, 3]

i=2: digits[2]=3 < 9, digits[2]=4
return [1, 2, 4]

Case 2：[1, 2, 9]

i=2: digits[2]=9, digits[2]=0
i=1: digits[1]=2 < 9, digits[1]=3
return [1, 3, 0]

Case 3：[9, 9, 9]

i=2: digits[2]=9, digits[2]=0
i=1: digits[1]=9, digits[1]=0
i=0: digits[0]=9, digits[0]=0
循环结束，digits = [0, 0, 0]
return [1, 0, 0, 0]

复杂度分析：

  • 时间复杂度：O(n)——最坏情况遍历所有位
  • 空间复杂度：O(1)——原地修改（全 9 情况除外）

为什么不直接转数字？ ​

你可能会想：把数组转成数字，加一，再转回数组，不是更简单吗？

javascript
// 错误做法
function plusOne(digits) {
    const num = parseInt(digits.join('')) + 1;
    return String(num).split('').map(Number);
}

问题：大数溢出。

JavaScript 的 Number 类型最大安全整数是 2^53 - 1（约 9 × 10^15）。如果输入的数组表示的数字超过这个值，就会出错。

数组模拟加法可以处理任意大的数字，这也是这道题的考点之一。

常见错误 ​

  1. 忘记处理全 9 情况
javascript
// 错误：没有处理全 9
function plusOne(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    // 忘记处理全 9，返回 [0, 0, 0]
    return digits;
}
  1. 从左往右遍历

加法要从低位开始，也就是数组的末尾。从左往右是错的。

相关题目 ​

这道题是"大数加法"的简化版。类似的题目还有：

  • 67. 二进制求和：二进制加法
  • 415. 字符串相加：两个字符串表示的数相加
  • 2. 两数相加：链表表示的数相加

它们的核心都是模拟进位。

本章小结 ​

这一章我们学习了进位处理的基本逻辑：

  1. 从低位到高位处理
  2. 小于 9：直接加一，结束
  3. 等于 9：变成 0，继续处理前一位
  4. 全是 9：需要在最前面加 1

这个模式在很多大数运算的题目中都会用到。

下一章，我们来看一道需要发现规律的题目：「找到所有数组中消失的数字」。

在 GitHub 上编辑此页