daily leetcode - plus-one - !

题目地址

https://leetcode.com/problems/plus-one/

题目描述

Given a non-empty array of digits representing a non-negative integer, plus 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 contain a single digit.

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

Example 1:

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

Example 2:

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

思路

将一个数字的每个位上的数字分别存到一个一维向量中,最高位在最开头,我们需要给这个数字加一,即在末尾数字加一,如果末尾数字是 9,那么则会有进位问题,而如果前面位上的数字仍为 9,则需要继续向前进位。具体算法如下:首先判断最后一位是否为 9,若不是,直接加一返回,若是,则该位赋 0,再继续查前一位,同样的方法,知道查完第一位。如果第一位原本为 9,加一后会产生新的一位,那么最后要做的是,查运算完的第一位是否为 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,然后相当于 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;
    }
}

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - plus-one - !
文章作者: lonuslan
文章链接: https://louislan.com/articles/2020/02/12/1581476167739.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LouisLan
    评论
    0 评论
avatar

取消