Leetcode 66- 加一

1. 题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

1
2
3
4
5
6
7
8
9
10

示例?1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例?2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

2. 思路

记录这篇文章，并不是因为题目有多难，而是代码组织的问题。。。这个题无非就是下面几种情况要考虑：

• 1.加最后一位时就没有进位
• 2.一直加到中间某位才没有进位
• 3.一直加到最前面的位还有进位，则要将数组扩容一位。并最高位置1.

  3. 代码

  按照上述思路，我写出来以下的垃圾代码，虽然说AC了，但是我自己再也不想看到这段代码了：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

  public class AddOne66 { public int[] plusOne(int[] digits) { int len = digits.length; int[] res = new int[len + 1]; int curOpBit = len - 1; // current operated bit (from right to left) boolean carry = (digits[len - 1] + 1 == 10); // After add one, if have to carry or not if (carry) { while (curOpBit <= len && curOpBit >= 0) { int tmp; if (carry) tmp = digits[curOpBit] + 1; else tmp = digits[curOpBit]; carry = (tmp == 10); // update carry flag if (carry) res[curOpBit + 1] = 0; else res[curOpBit + 1] = tmp; curOpBit--; if (!carry) // if no carry, exit right now break; } // After operating all the bits, if carry still exist, // add another bit before the leftmost. if (carry) { res[0] = 1; return res; } else { for (int i = curOpBit; i >= 0; i--) { res[i + 1] = digits[i]; } return Arrays.copyOfRange(res, 1, res.length); } } else { digits[len - 1] = digits[len - 1] + 1; return digits; } } public static void main(String[] args) { AddOne66 a = new AddOne66(); int[] digits = {9, 9}; int[] res = a.plusOne(digits); System.out.println(Arrays.toString(res)); } }

别人的优雅代码，差不多长这样：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

• ← Previous Post
• Next Post →