LeetCode No.66 | StriveZs的博客

LeetCode No.66

LeetCode第六十六题

自己代码的开源仓库:click here 欢迎Star和Fork :)

题目描述

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

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

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

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

示例 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

代码

两种方法一个是在内存上击败90%的人,一个是在时间上击败98%的人

内存上

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
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]

核心思想:
就是将数字转换为对应的数字,然后加1,再将其转换为列表
剪枝:对于尾数不为9的情况,直接在尾数加1返回即可
如果为9的话,则再转换为数字后加1再逆变换集合

另外还有一种思想:在原数组上直接考虑进位即可,如果9+1的话原位等0,进1如果前一位不为9则直接上即可
如果为9则重复上述直到加到最高位的话,则直接在结果前插入1即可。
"""
if digits[-1] != 9:
digits[-1] = digits[-1] + 1
return digits
str1 = ''
for i in range(len(digits)):
str1 += str(digits[i])
temp = str(int(str1) + 1)
result = []
for i in range(len(temp)):
result.append(int(temp[i]))
return result

if __name__ == '__main__':
s = Solution()
print(s.plusOne([9]))

时间上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]

核心思想:
就是将数字转换为对应的数字,然后加1,再将其转换为列表
剪枝:对于尾数不为9的情况,直接在尾数加1返回即可
如果为9的话,则再转换为数字后加1再逆变换集合

另外还有一种思想:在原数组上直接考虑进位即可,如果9+1的话原位等0,进1如果前一位不为9则直接上即可
如果为9则重复上述直到加到最高位的话,则直接在结果前插入1即可。
"""
i = len(digits)-1
while digits[i] == 9:
digits[i] = 0
i -= 1
if i == -1:
digits = [1] + digits
else:
digits[i] += 1
return digits
StriveZs wechat
Hobby lead  creation, technology change world.