【数组】66.加一

[lyonyang]

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

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

你可以假设除了整数 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[lyonyang]

思路一 - 反向遍历

反向遍历数组 , 遇 9 进 1 , 遇到不等于 9 就结束遍历

注意 : 如果没有被 break 打断 , 需要在数组前补一位

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)):
            if digits[~i] == 9:
                digits[~i] = 0
            else:
                digits[~i] = digits[~i] + 1
                break
        else:
            digits.insert(0, 1)
        return digits
# 注: ~ 操作符为按位取反,就可以得到反向对称的索引

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(1)$

思路二 - 类型转换

数组转数字 , 加 1 操作后再打散成数组 , 不过这样做就脱离题意了

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(n) for n in str(int(''.join(list(map(lambda x: str(x), digits)))) + 1)]

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(N)$

[chuchumeme]

思路:

有三种情况：

• 不会进位 比如 222 -> 223
• 会进位 比如 229 -> 230
• 会多一位 比如 999 -> 1000
• 设置一个标志位，用来判断是否需要进位，%=10是为了保证 9+1变成10时为0

复杂度

时间复杂度: O(n) 空间复杂度: O(1)

代码:

var plusOne = function(digits) {
    let ifBig = false;
    let len = digits.length;
    digits[len-1]++;
    for (let i = len - 1; i >= 0; i--) {
        if (ifBig) digits[i]++;
        ifBig = digits[i] > 9
        digits[i] %= 10
    }
    if (ifBig) digits.unshift(1)
    return digits;
};

[xuezc1119]

思路

倒着数是9的转换成0
遇到第一个不是9的，加一，跳出循环
[9,9,9]则进一

复杂度

时间复杂度: O(n) 空间复杂度: O(1)

代码

/**
 * @param {number[]} digits
 * @return {number[]}
 */
 var plusOne = function(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
      if (digits[i] < 9) { // 倒着数不是9的，就加一返回
          digits[i]++;
          return digits; // 遇到第一个不是9的，后面都不执行了，直接返回
      }
      digits[i] = 0; // 是9的都变成0
      
  }
  if (digits[0] == 0) { // 如果是[9,9,9]这种情况，上面的处理会变成[0,0,0] 所以要前面进1
      digits.unshift(1);
  }
  return digits;
};