题目描述

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.

题目思路

代码 C++

• 思路一、

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int jinwei = 0;
        int wei = digits.size()-1;
        
        // 如果最后一位小于 9，则没有进位
        if(digits[wei] < 9){
            digits[wei] +=1;
        }
        else{ // 最后一位为 9
            jinwei = 1;
            digits[wei] = 0;
            while(jinwei!=0){
                wei--;
                if(wei < 0){
                    digits.insert(digits.begin(), 1); // 首位之前插入 1
                    jinwei = 0;
                }
                else{
                    if(digits[wei] < 9){
                        digits[wei] += 1;
                        jinwei = 0;
                    }
                    else{ // digits[wei] == 9      
                        digits[wei] = 0;
                    }
                }
            }
        }
        return digits;
    }
};

• 思路二、

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i=digits.size()-1; i >= 0; i--){
            if(digits[i] < 9){
                digits[i] += 1;
                return digits;
            }
            else{ // digits[i] == 9
                digits[i] = 0;
            }
        }
        // 到此证明数组全为9,需要首位进１
        digits[0] = 1;
        digits.push_back(0);
        return digits;
    }
};

总结展望