leetcode筆記：Plus One

leetcode筆記：Plus One

一.題目描述

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

二.題目分析

一道高精度計算的題，從低位到高位進行計算，同時考慮進位的問題，若最高位計算結果還有進位，就需要在最高位前面添加一位。可做到時間復雜度為O(n)，空間復雜度為O(1)。

這道題應該算是簡化版，因為要求只是對一個數加1，如果任何一位的運算沒有進位，則更高位也不需要進行進位處理了，可以直接輸出結果。

三.實例代碼

#include 
#include 
using namespace std;

class Solution 
{
public:
    void plusOne(vector& digits)
    {
        int carry = 1;
        const int digitsSize = digits.size();
        for (int i = digitsSize - 1; i >= 0; i--)
        {
            digits[i] += carry;
            if (digits[i] < 10)
            {
                carry = 0;
                break;
            }
            carry = digits[i] / 10;
            digits[i] %= 10;
        }
        if (carry != 0) // 若最高位運算仍有進位，則需新增一位並置1
            digits.insert(digits.begin(), carry);
    }
};

兩個運行結果：

四.小結

又是一道涉及位運算的題目，解決方法有多種，而且應該考慮plus不同的值時，又該怎麼處理。