(数组) leetcode 66. Plus One

佚名 6年前 (2019-04-26) 随笔 1029人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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.

------------------------------------------------------------------------------------------------
这个题关键是如何进位以及判断数组的首位前是否进1。可以用一个辅助标记来帮助我们做到这些。

C++代码：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 0;
        int len = digits.size();
        for(int i = len - 1; i >= 0; i--){
            int a = digits[i];
            if(i == len - 1){
                int sum = a + carry + 1;
                digits[i] = sum % 10;
                carry = sum / 10;  //进一位。
            }
            else{
                int sum = a + carry;
                digits[i] = sum % 10;
                carry = sum / 10;
            }
        }
        if(carry != 0){  //表明前面还得进位。
            digits.insert(digits.begin(),carry);
        }
        return digits;
    }
};