LeetCode 66. 加一

Regan Yue

发布于 2023-07-10 14:44:57

1490

发布于 2023-07-10 14:44:57

文章被收录于专栏：ReganYue's Blog

LeetCode 66. 加一

一、题目描述：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数 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] 提示： 1 <= digits.length <= 100 0 <= digits[i] <= 9 来源：力扣（LeetCode）链接：https://leetcode.cn/problems/plus-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

这道题考察了什么思想？你的思路是什么？

题目很简单，找到数组最后一个元素加1即可，但是我这里提出一种进阶的要求，返回的是数字怎么办？

我的思路很简单，从末尾开始，每前一位flag乘10，然后再乘数组中的数字。比如：

4321：取1 然后加1 然后flag 为1 ，取2，然后flag乘以10，为10 2乘10得20，取3，然后flag乘10，为100 3乘以100得300，取4 然后flag乘以10，为1000 得4000，加起来就算4000+300+20+2=4322。

func plusOne(digits []int) []int {
    var flag = 1
    var sum = 0
    digits[len(digits)-1] += 1
    for i:=len(digits)-1;i>=0;i--{
        var num = digits[i]
        sum += (num*flag)
        flag *= 10
    }
    return sum
}

做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

不是，我发现我看错题目了！！！

当我们对数组digits 加一时，我们只需要关注 digits 的末尾出现了多少个 9 即可。

如果不为9，直接加1即可，若末尾有n个9，我们直接将第一个不为9的值加1，然后其他9置0即可，如果都是9，那么我们就构造一个比digits长度多1的新数组，将首元素置为1，其余元素为0即可。

有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

按照常规的方式模拟两个数字进行加法，给定数组内的数字和1进行加法，然后记录下进位。

func plusOne(digits []int) []int {
    // 初始进位1
    add:=1
    for i:=len(digits)-1;i>=0;i-- {
        curr:= digits[i] +add  
        // 如果等于10说明要进位
        if curr ==10 {
            // 当前位位0
            digits[i]=0
            //进位1
            add =1
        }else{
            // 无需进位
            digits[i]=curr
            add =0
        }
        // 等于0说明了加法完毕
        if add ==0 {
            break
        }
    }
    // 如果进位仍然大于0 ,说明要在数组的开头补充1
    if add >0 {
        return append([]int{1},digits...)
    }
    return digits
}


作者：gopher666
链接：https://leetcode.cn/problems/plus-one/solution/by-gopher666-svmp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、AC 代码：

func plusOne(digits []int) []int {
    n := len(digits)
    for i := n - 1; i >= 0; i-- {
        if digits[i] != 9 {
            digits[i]++
            for j := i + 1; j < n; j++ {
                digits[j] = 0
            }
            return digits
        }
    }
    digits = make([]int, n+1)
    digits[0] = 1
    return digits
}

四、总结：