加一—LeetCode66

发布于 — 2018 年 08 月 27 日
#LeetCode

题目描述

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

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

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

示例 1:

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

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

一个数组，每一位表示一个数字，高位在前面，然后需要将这个值加一，并且按照数组的形式返回。

解题思路

日常生活中，如果拿到一个值，加一。首先是操作个位。

这时候有几种情况，

  • 个位数小于9，长度不变，最后一位加1即可。比如18+1=19。

  • 个位数等于9，进位过程中在中间某一位完成，比如19+1=20。这时长度没变。

  • 个位数等于9，进位过程中一直向上进位，最后长度加1，比如99+1=100。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int[] plusOne(int[] digits) {
  int n = digits.length;
  //从个位开始加1
  for(int i=n-1; i>=0; i--) {
    if(digits[i] < 9) {
      //如果小于9,则加一然后返回
      digits[i]++;
      return digits;
    }
    //否则，将这位置为0，然后向上进位
    digits[i] = 0;
  }
  //这时已经超过数组长度，所以需要新建一个数组，长度加一，第一位1，后面全部为0
  int[] newNumber = new int [n+1];
  newNumber[0] = 1;
  return newNumber;
}