施坤的博客
0%

leetcode-66-加1

发表于 分类于 阅读次数： Valine：

说明

  • 本人零基础，数学基础极差，此系列开始学习下leetcode算法方面的题目
  • 都是leetcode的原题

0066. 加一

  • 难度：简单
  • 标签：数组
  • 本题来自这里

题目大意

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：digits = [0]
输出：[1]

解体思路

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

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

  • 还有一个注意的点：首位进位变成10之后也需要进行处理，因为会多一位数字

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        # 最后一位值+1
        digits[len(digits) - 1] += 1
        # 以-1不停递减直到0，初始化值为最后一位索引
        for i in range(len(digits) - 1, 0, -1):
            # 末尾索引的值不为10，就退出循环
            if digits[i] != 10:
                break
            else:
                # 末尾的值为10，就把赋值为0
                digits[i] = 0
                # 末尾-1后的索引值+1
                digits[i - 1] += 1

        # 如果首位为10
        if digits[0] == 10:
            # 首位赋值为1
            digits[0] = 1
            # 在第二位新增值为0
            digits.append(0)
        return digits



if __name__ == "__main__":

    data = [9,9,9]
    t = Solution().plusOne(data)
    print(t) # [1, 0, 0, 0]

 	data = [1,2,4]
    t = Solution().plusOne(data)
    print(t) # [1,2,5]
    
    data = [0]
    t = Solution().plusOne(data)
    print(t) # [1]

参考资料

可以参考此系列，刷算法