leetcode 66 Plus One
z
 2017-12-24 20:55:04  

66. Plus One

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.

开始的想法是将digits数组转换为int类型在自增1.

但是这样digits表示的数字是可能超过int类型的范围的，long一样，因此不可取。

下面解法的主体思路如下：

  • 设置一个int类型的carry表示进位，初始化为0
  • 对digits最后一位自增
  • 从digits最后一位开始判断当前的数字加上carry是否大于10
  • 如果大于10，对其模10，并将carry置1
  • 如果小于10，将carry置0
  • 循环结束后，判断当前carry是否为1
  • 如果为1，需要新建一个数组，第一位置1后，将digits复制到新建数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int carry = 0;
        digits[n-1]++;
        for(int i=n-1;i>=0;i--){
            digits[i] = digits[i] + carry;
            if(digits[i] > 9){
                digits[i] = digits[i] % 10;
                carry = 1;
            }
            else{
                carry = 0;
            }
        }
        if(carry != 0){
            int[] result = new int[n+1];
            result[0] = carry;
            for(int i=1;i<n+1;i++){
                result[i] = digits[i-1];
            }
            return result;
        }
        return digits;

but！

discuss区更优的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution{
  public int[] plusOne(int[] digits){
    int n = digits.length;
    for(int i=n-1; i>=0; i--){
      if(digits[i] < 9){
        digits[i]++;
        return digits;
      }
      else{
        digits[i] = 0;
      }
    }
    int[] result = new int[n+1];
    result[0] = 1;
    return result;
  }
}
  • 从后往前倒序遍历数组digits
  • 如果当前数字小于9，在当前数字+1后，返回digits
  • 如果当前数字大于9，也就是等于9，将当前数组置0
  • 如果循环结束都没有返回，说明digits数组已经被全部置为0了，需要新建一个数组，将第0位置1后返回。