PlusOne [source code]

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

    public static void main(String[] args) {
        PlusOne.Solution tester = new PlusOne.Solution();
        int[] input1 = {9,9,9,9};
        Printer.array (tester.plusOne(input1));
    }
}

刚开始看错题目了, 以为这个题目要求的是digits代表的是一个 binary 的数字, 还觉得这个题目有点想头来的:

java public class Solution { public int[] plusOne(int[] digits) { int n = digits.length; int i = n - 1; for (; i >= 0; i--) { if (digits[i] == 1) { digits[i] = 0; } else { digits[i] = 1; break; } } if (i >= 0) return digits; int[] res = new int[n + 1]; res[0] = 1; for (i = 1; i < n + 1; i++) res[i] = digits[i - 1]; return res; } }这个是我自己写的代码, 核心思路就是学 CLRS 的时候学到的一个思想: binary number的 increment 在碰到的第一个0的位置停止;

结果没想到这个题目这么蠢, 那就只能用一位一位的来做了;
好像也可以对这个题目做一个类似的优化;

循环内部的写法上面, 首先判断当前是否停止(也就是不可能有进位产生); 然后再判断可能有进位的情况;

这题特别交代了没有 leading0, 所以想想应该就是希望做出这个解法; 因为如果有 leading0s 的话, 就不能这么简单的来做了; 不对, 好像也可以; 就是最后的最高进位的处理上面稍微麻烦一些, 因为不能直接用 array 的边界来进行处理了;
另外十进制的情况跟 binary 好像还是有区别;

理解了这个算法最后的本质之后就还是很好写的. 相对于最 naive 的解法, 这个解法的好处在于, 不用拿着一个 carry 一位一位的去计算; +1这个东西好像是有点特殊的.

最后的速度是0ms (42%), 应该是最优解了;

看了一下 discussion, 这个就是最优解了;

Problem Description

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

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

The digits are stored such that the most significant digit is at the head of the list.

Difficulty:Easy
Category:Algorithms
Acceptance:38.29%
Contributor: LeetCode
Companies
google
Related Topics
array math
Similar Questions
Multiply Strings Add Binary Plus One Linked List