Plus One

• Easy
• keyword: Math
• 类似: ...

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。 该数字按照大小进行排列，最大的数在列表的最前面。

• 例子:
  • 给定 [1,2,3] 表示 123, 返回 [1,2,4].
  • 给定 [9,9,9] 表示 999, 返回 [1,0,0,0].
• 我觉得英文题目表述写的不好. 什么list?

idea

• 按照正常的加法, 一位一位的加, 最后判断carry是否为1来处理最终的进位(实际上只有全部位为9才会有最高位进位). 这也是我在Lintcode里面的写法.
• 看了Leetcode discuss才发现更好的方法, key是: 不用考虑进位!
  • 如果当前位不是9, 加了1就直接return!, 否则设置为0, 再去下一位.
  • 如果全部位都结束了, 但还没有return, 说明所有位都是9, 故增加一位, 并设为1, 其他位default是0, 不用设.
• 代码如下:

public int[] plusOne(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
        if (nums[i] < 9) {
            nums[i]++;
            return nums;
        }
        nums[i] = 0;
    }
    int[] ans = new int[nums.length+1];
    ans[0] = 1;
    return ans;
}

总结

• 数学题目重要的是找到规律, 这样可以最大限度的利用问题的性质解决, 而不是通用的方法.