LeetCode 66 Plus One（加一）（vector）

LeetCode 66 Plus One（加一）（vector）

翻譯

給定一個以一系列數字表示的非負數，將其加一並轉換成數字。

數字存儲的最高位在列的最前面。

原文

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

分析

一看到這個題目我就想起來前面做過的一道關於求出一個數中包含的所有數字的題目，然後這裡就用了這個方法。

首先將vector中的數字組合成數，然後對這個數進行加一操作，然後將這個數轉換成vector的形式存儲。

    int powTen(int num, int times) {
        for (int i = 0; i < times; ++i) {
            num *= 10;
        }
        return num;
    }

    int getNumFromVector(vector& digits) {
        int num = 0;
        for (int i = 0; i < digits.size(); ++i) {
            num += powTen(digits[i], digits.size() - i - 1);
        }
        return num;
    }

    vector getVectorFromNum(int num) {
        vector v;
        stack s;
        while (num >= 10) {
            s.push(num % 10);
            num /= 10;
        }
        s.push(num);
        while (!s.empty()) {
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }

    vector plusOne(vector& digits) {
        int num = getNumFromVector(digits);
        num += 1;
        return getVectorFromNum(num);
    }

然而後來發現並不能通過，於是將int改成了long，改來改去還是不信，好吧題意不希望我這樣寫吧……沒事，那就改，有的是思路。

具體代碼見後文，首先對vector的最後一個數字進行加1操作。然後再開始遍歷，並判斷是否大於10，進行相應的操作。Ok，這裡能做的都做了。

最後如果第一個數字是9然後加上1變成了10，或者其他大於10的情況，就啟用了下面的if判斷，這個占了整個代碼的一半。因為需要對整個vector進行重組。其實我反而覺得這種方法寫起代碼來比較簡單，只不過不太好直觀地了解，所以我還是更喜歡上面的代碼，即便不符合題目的用意，但是畢竟更加的抽象。

代碼

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