66. 加一

1.题目

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

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

示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0]
输出：[1]

提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9

2.解题思路

根据题意加一，没错就是加一这很重要，因为它是只加一的所以有可能的情况就只有两种：

• 除 9 之外的数字加一
• 数字 9
  加一得十进一位,个位数为 0,加法运算如不出现进位就运算结束了且进位只会是一。
  所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 1 个位数置为 0，如此循环直到判断没有再进位就退出循环返回结果。
  然后还有一些特殊情况就是当出现 9999、999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。

3.代码

3.1 正确的范例

def plusOne(digits: Array[Int]): Array[Int] = {
    for(i<-digits.length-1 to 0 by -1){
      digits(i)=digits(i)+1
      digits(i) =digits(i)%10
      if(digits(i)!=0)  return digits
    }
    val array = new Array[Int](digits.length+1)
    array(0) = 1
    array
  }

3.2 错误的范例

  // 出现   字符串转整数  然后进行加1操作 出现数据溢出错误
  // 因为  1 <= digits.length <= 100   远远大于 long类型长度了
  // 所以会出现错误
  def plusOne2(digits: Array[Int]): Array[Int] = {
    var strNum = ""
    for(i<-0 to digits.length-1){
      strNum = strNum+digits(i)
    }
    val num = strNum.toLong+1   // TODO  这个位置数据溢出
    val array = new Array[Int](num.toString.length)
    for(i<-0 to num.toString.length-1){
      array(i) = num.toString.substring(i,i+1).toInt
    }
    array
  }

4.总结

时间复杂度：O(logx)，即为二分查找需要的次数。

空间复杂度：O(1)。