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

将一个数字的每个位上的数字分别存到一个一维向量中,最高位在最开头,我们需要给这个数字加一,即在末尾数字加一,如果末尾数字是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;
    }
}

Github 同步地址:

https://github.com/grandyang/leetcode/issues/66

类似题目:

Add Binary

Multiply Strings

Plus One Linked List

参考资料:

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

https://leetcode.com/problems/plus-one/discuss/24082/my-simple-java-solution

https://leetcode.com/problems/plus-one/discuss/24084/Is-it-a-simple-code(C%2B%2B)

LeetCode All in One 题目讲解汇总(持续更新中...)

标签智能推荐:

LeetCode高频题目(100)汇总-Java实现

&nbsp;LeetCode高频题目(100)汇总-Java实现&nbsp;&nbsp;&nbsp;【Leetcode-easy-1】TwoSum【Leetcode-easy-2】AddTwoNumbers【Leetcode-easy-3】LongestSubstringWithoutRepeatingCharacters【Leetcode-easy-5】LongestPalindromicSub

C++ 前期准备

在线编译网站:http://www.dooccn.com/cpp/刷题:https://leetcode.com/https://leetcode-cn.com/

Index

Tableofcontents目录TableofcontentsOJ-Improvemyself,better.Leetcode洛谷OJ-Improvemyself,better.Leetcode洛谷

算法-1

1.能少for循环,就少2.与for无关的变量的不进入for循环刷题网址:1.leetcode:https://leetcode.cn/https://leetcode-cn.com/2.牛客网:https://www.nowcoder.com/

8.2

python版按键精灵,pyautogui。未完成,看书deeplearning,刷题leetcode。明日:网络脚本,看书,刷题。

二分搜索常见题

LeetCode:1011.在D天内送达包裹的能力&nbsp;https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/875.爱吃香蕉的珂珂&nbsp;https://leetcode-cn.com/problems/koko-eating-bananas/1482.制作m束花所需的最少天数&nbsp;htt

09-06日记

1.leetcode复习五道2.你不知道的js学习3.webpack学习

总结-二叉树

二叉树:前序遍历:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/中序遍历:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/后序遍历:https://leetcode-cn.com/problems/binary-tree-postorder

11-29日记

1.leetcode两道2.koa源码学习3.跨域知识学习

ArrayList、ArrayDeque与LinkedList区别

https://blog.csdn.net/u011485472/article/details/109124458https://leetcode-cn.com/circle/article/bXc4tx/