0066. 加一

0066. 加一 #

  • 标签:数组
  • 难度:简单

题目大意 #

描述:给定一个非负整数数组,数组每一位对应整数的一位数字。

要求:计算整数加 1 后的结果。

说明

  • $1 \le digits.length \le 100$。
  • $0 \le digits[i] \le 9$。

示例

1
2
3
输入digits = [1,2,3]
输出[1,2,4]
解释输入数组表示数字 1231 之后为 124

解题思路 #

思路 1:模拟 #

这道题把整个数组看成了一个整数,然后个位数加 1。问题的实质是利用数组模拟加法运算。

如果个位数不为 9 的话,直接把个位数加 1 就好。如果个位数为 9 的话,还要考虑进位。

具体步骤:

  1. 数组前补 0 位。
  2. 将个位数字进行加 1 计算。
  3. 遍历数组
    1. 如果该位数字大于等于 10,则向下一位进 1,继续下一位判断进位。
    2. 如果该位数字小于 10,则跳出循环。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def plusOne(self, digits: List[int]) -> List[int]:
    digits = [0] + digits
    digits[len(digits) - 1] += 1
    for i in range(len(digits)-1, 0, -1):
        if digits[i] != 10:
            break
        else:
            digits[i] = 0
            digits[i - 1] += 1
        
    if digits[0] == 0:
        return digits[1:] 
    else:
        return digits

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$。一重循环遍历的时间复杂度为 $O(n)$ 。
  • 空间复杂度:$O(1)$。
本站总访问量  次  |  您是本站第  位访问者