leetcode|66. Plus One

我就是我 2022-05-27 13:47 148阅读 0赞

问题描述：

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
    Output: [1,2,4]
    Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
    Output: [4,3,2,2]
    Explanation: The array represents the integer 4321.

问题解析：

刚开始看看不懂题意，题意是vector中存的数字们把他们合起来当成一个整数，返回该整数加1之后的整数，以相同格式存在vector里。

典型测试用例：9（10）,99（100）,125（126）

所以大致分两类，有进位和无进位。

有进位里面要统计进位的个数。

class Solution {
    public:
        vector<int> plusOne(vector<int>& digits) {
            
            int l=digits.size();
            int temp=0;
            for(int i=l-1;i>=0;i--){
                if(digits[i]!=9){
                    break;
                }
                else{
                    temp++;
                }
            }
            if(temp!=0){
                         
                for(int i=l-temp;i<l;i++){
                    digits[i]=0;
                }
                if(l-temp!=0)
                    digits[l-temp-1]+=1;
                else digits.insert(digits.begin(),1);
                
            }
            else digits[l-1]+=1;
            
            return digits;  
            
        }
    };

刚开做的时候想的是对于有进位的地方，考虑该位置p（变0），以及p-1（+1）和p+1（push\_back(0)）.

这样把问题搞复杂了，因为要考虑p-1是否存在。

其实把牵扯进位的值换成0，前面进位看是否是首部，若为首部则插入1，否则+1即可。