66 加一

题目描述#

欸，这题模拟的是咱小学列竖式的场景——给你一个数组 digits，从左到右按最高位到最低位存着一个大整数的每一位（没有前导 0）。咱要给这个大整数 加 1，再把结果按同样的格式返回成数组。

思路#

咱第一眼看，这就是"末位加一 + 处理进位"的活儿。既然加的是 1，那咱只需要从最低位（数组末尾）开始往前扫，模拟手算进位就行。

关键的观察是：只要某一位不是 9，给它加一就彻底结束了，根本不会再向前进位。所以本姑娘的循环逻辑是这样——从 i = len-1 往前走，遇到 digits[i] != 9，直接 digits[i]++ 然后 return digits，干脆利落收工；如果这一位是 9，加一会变 10 产生进位，那就把这一位置 0，继续往前一位接着处理进位。

那什么时候会跑完整个循环都没返回呢？只有一种情况：原数组从头到尾全是 9（比如 [9,9,9]）。这时每一位都被置成了 0，但最高位还有一个进位没地方放，所以咱在循环外头补一句 append([]int{1}, digits...)，在最前面塞个 1，结果就是 [1,0,0,0]。这是唯一会让数组长度增加的情形。

整个过程从后往前最多扫一遍，时间复杂度 $O(n)$，除了全 9 那种要新建数组，其余情况都是原地修改、空间 $O(1)$。

知识边界#

从低位模拟进位：从数组末尾往前加，是大整数 / 数组形式数字做加法的标配思路。
提前返回剪枝：碰到非 9 的位加一即可终止——加 1 不可能让一个非 9 的位再向前进位，所以无需扫完整个数组。
全 9 的特判：只有原数组全是 9 时才会跑完循环，此时需在最前面 append 一个 1，且这是唯一令结果长度 +1 的情况——容易漏掉哦。
append([]int{1}, digits...)：Go 里在切片头部插入元素的常用写法，先建带 1 的新切片，再把原 digits 展开拼在后面。

代码#

下面这版咱一行没动，从低位往前模拟进位：

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] != 9 {
            digits[i]++
            // 这里如果digits不是9说明进位已经结束了，可以直接返回
            return digits
        }
        // 如果这一位是9,则进位置0
        digits[i] = 0
    }

    // 当运行到这里的时候，说明原数组全是9
    return append([]int{1}, digits...)
}

好啦，数学专区又添一道～咱去整理今天的照片咯，下次再来收拾更刁钻的数论题！