Leetcode 43. Multiply Strings

老老实实的做

class Solution {
public:
    vector plusOne(vector& digits) {
        for(int i=digits.size()-1;i>=0;i--){
            if(digits[i] == 9){
                digits[i] = 0;
            }else{
                digits[i]++;
                return digits;
            }
        }
        digits.push_back(0);
        digits[0] = 1;
        return digits;
    }
};

时间复杂度：O(2*N)
空间复杂度：O(N)

只需考虑类似[1,9]或者[9,9]的特殊情况，这种做法节省空间，无需拷贝原数组

class Solution {
public:
    vector plusOne(vector& digits) {
        for(int i=digits.size()-1;i>=0;i--){
            if(digits[i] == 9){
                digits[i] = 0;
            }else{
                digits[i]++;
                // returned here if not all 9 in the digits
                return digits;
            }
        }
        // all 9 in the digits, need to add a extra digit in
        digits.push_back(0);
        digits[0] = 1;
        return digits;
    }
};