66. Plus One

題目網址：https://leetcode.cn/problems/plus-one/

題意：給一整數 array digits 用來表示一非負整數。返回該非負整數 + 1 後所表示的 digits。

非負整數的最高為儲存在 digits 的首位, 其中 digits[i] 只儲存單個數字。

除了 0 之外, 其他整數都不會以 0 作為開頭。

Solution 1：

想法：遍歷 digits, 並紀錄進位 carry。若最後 carry 為 1, 則在 digits 最前面補上 1

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1; // 因為最後一位要加 1, 所以把 carry 設成 1
        for (int i = digits.size() - 1; i >= 0; --i) {
            digits[i] = carry + digits[i];
            carry = digits[i] / 10;
            digits[i] %= 10;
        }

        if (carry) {
            digits.emplace(digits.begin(), carry);
        }

        return digits;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：改進 Solution 1, 改成一旦不用進位, 則終止循環（循環裡會不斷將 digits[i] + 1）, 並返回 digits

• digits[i] < 9：代表不用進位, 將 digits[i] + 1 後, 終止循環並返回 digits
• digits[i] == 9：代表要進位, 將 digits[i] 設為 0, 並繼續循環

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

        // 執行到這裡, 代表原先 digits 裡的元素全為 9, 現在全變為 0 了
        // 因此在最前面加入 1 即可, e.g. 999 ➔ 000 ➔ 1000
        digits.emplace(digits.begin(), 1);

        return digits;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(1)$ ➔ 只需常數空間