Leetcode 66. 加一(C++) （小白学习之路）

喜欢ヅ旅行 2023-07-11 11:21 20阅读 0赞

题目描述：

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

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

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: \[1,2,3\]  
输出: \[1,2,4\]  
解释: 输入数组表示数字 123。  
示例 2:

输入: \[4,3,2,1\]  
输出: \[4,3,2,2\]  
解释: 输入数组表示数字 4321。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/plus-one  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

拿到这道题，有两种思路，一种是常规的从后往前遍历，遇9化0，前一位加一，从后往前遍历的好处就是一旦检测到没有进位就可以直接返回结果，以下是从后往前遍历的代码，比较简洁易懂：

class Solution {
    public:
        vector<int> plusOne(vector<int>& digits) {
            int length = digits.size();  //数组长度，写的简洁点的话可以省掉这行直接写到循环里
            for(int i=length-1;i>=0;i--)
            {
                digits[i]++;              //末尾加一
                digits[i]= digits[i]%10;   //取个位数
                if(digits[i]!=0) return digits; //如果个位不为0的话直接返回加一后的结果，如果个位为0，那么继续遍历前一位
            }
            digits.insert(digits.begin(),1); //到这一步说明最高位也进位了，因此要在第一个部分插入1
            return digits;
    
        }
    };

![20200305133628202.png][]

从结果看用时有点长，这种算法的时间复杂度O（n），空间复杂度为常数，属于比较常规的写法。我看了用时1ms的大神代码好像跟我这差不多，有可能是机器不一样吧；

第二种思路就是递归，递归要素：递归终点，递归循环。这里很明显递归重点就是当digits.size()=1时，只需判断有没有进位，进位则在digits.begin()插入1，没进位则直接加1返回；

这题递归的循环可以这么看，把任一digits分为个位那一部分和十位往前的一部分，如果个位没有进位，那就把个位加一直接返回，如果个位进位了，就递归调用十位往前的部分加一，思路想好了，代码如下：

class Solution {
    public:
        vector<int> plusOne(vector<int>& digits) {
            int length = digits.size();
            if(length==1)                        //递归终点
            {
                if(digits[length-1]==9)           //个位进位则插入1，不进位则加一返回
                {
                    digits[length-1]=0;
                    digits.insert(digits.begin(),1);
                }
                else digits[length-1]++;
                return digits;
            }
            else                                //递归循环
            {
                if(digits[length-1]==9)         //个位为9，进位的情况
                {
                    digits[length-1]=0;
                    vector<int>vec(digits.begin(),digits.end()-1); //取不含个位的部分
                    vector<int>vec2 = plusOne(vec);  //继续递归调用plusOne
                    vec2.push_back(0);               //不要忘了个位的0
                    return vec2;
                }
                else
                {
                    digits[length-1]++;         //个位不为9，无需进位的情况
                    return digits;
                }
            }
    
        }
    };

![20200305133741791.png][]

结果如上，可以看出，同一台机器下，递归方法的时间复杂度比常规的要低，应该为常数级时间复杂度，这里用掉的时间应该是系统调用递归结果的耗时，递归方法的空间复杂度为O（n），相当于用空间换时间，在许多大型项目中会经常用到这种方法。递归的方法应该可以写的更简洁一点，等我二刷的时候再尝试下。

以上两种方法个人感觉都挺好用的，可以常备。

[20200305133628202.png]: https://img-blog.csdnimg.cn/20200305133628202.png
[20200305133741791.png]: https://img-blog.csdnimg.cn/20200305133741791.png