plus-one.md

Plus One

描述

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

分析

高精度加法。

代码

{% if book.java %} {% codesnippet "./code/plus-one."+book.suffix, language=book.suffix %}{% endcodesnippet %} {% endif %}

{% if book.cpp %}

// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        add(digits, 1);
        return digits;
    }
private:
    // 0 <= digit <= 9
    void add(vector<int> &digits, int digit) {
        int c = digit;  // carry, 进位

        for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
            *it += c;
            c = *it / 10;
            *it %= 10;
        }

        if (c > 0) digits.insert(digits.begin(), 1);
    }
};

{% endif %}