快捷導(dǎo)航

C++實現(xiàn)LeetCode(66.加一運算)

更新時間：2021年07月16日 17:01:33 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(66.加一運算),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 66. Plus One 加一運算

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Example 3:

Input: digits = [0]
Output: [1]

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9

將一個數(shù)字的每個位上的數(shù)字分別存到一個一維向量中，最高位在最開頭，我們需要給這個數(shù)字加一，即在末尾數(shù)字加一，如果末尾數(shù)字是9，那么則會有進(jìn)位問題，而如果前面位上的數(shù)字仍為9，則需要繼續(xù)向前進(jìn)位。具體算法如下：首先判斷最后一位是否為9，若不是，直接加一返回，若是，則該位賦0，再繼續(xù)查前一位，同樣的方法，知道查完第一位。如果第一位原本為9，加一后會產(chǎn)生新的一位，那么最后要做的是，查運算完的第一位是否為0，如果是，則在最前頭加一個1。代碼如下：

C++ 解法一：

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

Java 解法一：

public class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = digits.length - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                ++digits[i];
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
    }
}

我們也可以使用跟之前那道 Add Binary 類似的做法，將 carry 初始化為1，然后相當(dāng)于 digits 加了一個0，處理方法跟之前那道題一樣，參見代碼如下：

C++ 解法二：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        if (digits.empty()) return digits;
        int carry = 1, n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (carry == 0) return digits;
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry == 1) digits.insert(digits.begin(), 1);
        return digits;
    }
};

Java 解法二：

public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits.length == 0) return digits;
        int carry = 1, n = digits.length;
        for (int i = digits.length - 1; i >= 0; --i) {
            if (carry == 0) return digits;
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        return carry == 0 ? digits : res;
    }
}

到此這篇關(guān)于C++實現(xiàn)LeetCode(66.加一運算)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)加一運算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: