算法leetcode｜66. 加一（rust重拳出击）

文章目录

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

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 最开始闪过一个念头，直接拿数组的末位，加上一不就完事了？
• 虽然是个简单题，但也不能太不当回事了。
• 如果最后一位不是9，那的确就完事了，但如果是9的话，就要产生进位，而不是简单的加一了。
• 进位之后，前一位就要加一，又有可能产生进位，所以这道题主要就是处理进位。
• 最终有可能所有的数字都是9，从末尾一路进位到头，空间不够了，这种情况下就只能申请新的空间了，要多一位出来。
• 分析参数有三种可能性： 1. 末尾没有 9，例如 [1,2,3]，那么我们直接将末尾的数加一，得到 [1,2,4] 并返回。2. 末尾有若干个 9，例如 [1,2,3,9,9]，那么我们只需要逆向找出第一个不为 9 的元素，即 3，将该元素加一，同时途中的 9 都变为0，得到 [1,2,4,0,0] 并返回。3. 所有元素都是 9，例如 [9,9,9,9,9]，那么答案为 [1,0,0,0,0,0]。我们只需要构造一个长度比参数长度多 1 的新数组，将首元素置为 1，其余元素置为 0 即可。
• 所以这道题可以这样处理，从数组末位逆向查找第一个不是 9 的数字，加一，途中是 9 的位都变成0，进位。
• 如果所有的数字都是 9，那么直接申请新的空间，比源数组长度加一，然后首位赋值为1即可。

题解：

rust：

implSolution{pubfnplus_one(mut digits:Vec<i32>)->Vec<i32>{let n = digits.len();for i in(0..n).rev(){if digits[i]==9{// 进位变为0
                digits[i]=0;}else{// 第一个不是9的位
                digits[i]+=1;return digits;}}// digits 中所有的元素均为 9letmut ans =vec![0; n +1];
        ans[0]=1;return ans;}}

go：

funcplusOne(digits []int)[]int{
    n :=len(digits)for i := n -1; i >=0; i--{if digits[i]==9{// 进位变为0
            digits[i]=0}else{// 第一个不是9的位
            digits[i]++return digits
        }}// digits 中所有的元素均为 9
    digits =make([]int, n+1)
    digits[0]=1return digits
}

c++：

classSolution{public:
    vector<int>plusOne(vector<int>& digits){constint n = digits.size();for(int i = n -1; i >=0;--i){if(digits[i]==9){// 进位变为0
                digits[i]=0;}else{// 第一个不是9的位++digits[i];return digits;}}// digits 中所有的元素均为 9
        vector<int>ans(n +1);
        ans[0]=1;return ans;}};

python：

classSolution:defplusOne(self, digits: List[int])-> List[int]:
        n =len(digits)for i inrange(n -1,-1,-1):if digits[i]==9:# 进位变为0
                digits[i]=0else:# 第一个不是9的位
                digits[i]+=1return digits

        # digits 中所有的元素均为 9return[1]+[0]* n

java：

classSolution{publicint[]plusOne(int[] digits){finalint n = digits.length;for(int i = n -1; i >=0;--i){if(digits[i]==9){// 进位变为0
                digits[i]=0;}else{// 第一个不是9的位++digits[i];return digits;}}// digits 中所有的元素均为 9int[] ans =newint[n +1];
        ans[0]=1;return ans;}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~