66. Plus One

1.問題

• 給予一個list, 並在最末的數值+ 1, 問最終的list

2.想法

• 提問: 確定是在第一個元素還是最末個元素+ 1

• function header, parameter

• test input

• 說明想法

  • 因為在第一個元素+ 1會比較簡單, 因此計算前先對vector reverse以方便計算

  • 計算時須注意新的值是(carry + 自己) % 10, 並且更新carry

  • 當結束計算, carry不為零時, push到list中

  • reverse回來

• 測試計算複雜度

3.程式碼

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //vector<int> res;
        reverse(digits.begin(), digits.end());
        int ret = 0, curr = 0; 
        for (int i = 0 ; i < digits.size(); i++){
            if( i == 0){
                ret = (digits[0] + 1) / 10;
                digits[0] = ((digits[0] + 1) < 10) ? digits[0] + 1 : (digits[0] + 1) % 10;
            }else{
                int t = digits[i];
                digits[i] = ((digits[i] + ret) < 10) ? digits[i] + ret : (digits[i] + ret) % 10;
                ret = (ret + t) / 10;
            }
        }
        if(ret != 0){
            digits.push_back(ret);
        }
        reverse(digits.begin(), digits.end());
        return digits;
    }
};