LeetCode 66 Plus One（加一）（vector）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50564455

翻譯

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

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

原文

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<int>& digits) {
        int num = 0;
        for (int i = 0; i < digits.size(); ++i) {
            num += powTen(digits[i], digits.size() - i - 1);
        }
        return num;
    }

    vector<int> getVectorFromNum(int num) {
        vector<int> v;
        stack<int> 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<int> plusOne(vector<int>& 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<int> plusOne(vector<int>& 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<int> newVec;
            newVec.push_back(digits[0] - 9);
            digits[0] -= 10;
            for (auto i : digits) {
                newVec.push_back(i);
            }
            return newVec;
        }
        return digits;
    }
};