闲来无事刷刷 LeetCode 长长见识,遇到一道觉得有意义的题目,就此写下来作为自己的简单笔记

Question

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Analysis

该题目大意是实现大数(用数组存储)加1的功能。

在程序中每一个变量有一定的内存空间来存储,如果超过了字节限制,程序就是溢出。

于是乎,对于超大数字的计算会使用算法来处理,比如这道 LeetCode #66 的问题。

需要注意的就是满十进一这个规则,以及类似999+1=1000需要在第一位添一个1这种特例。

比方说:

99999 = [9,9,9,9,9]

99999 + 1 = [1,0,0,0,0,0]

99998 + 1 = [9,9,9,9,9]

解决这道题,只需要从后往前循环,如果当前数字(或尾数)小于9就可以退出。

在此会有两种解题方法,我先把自己的方法放出溜溜,代码行数略多,效率在 LeetCode 中是前 34% 的。

方法一[自己的]

链接→

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
flag = 0
n = len(digits) - 1
while n >= 0:
if(digits[n] < 9):
digits[n] = digits[n] + 1
break
else:
flag = 1
digits[n] = 0
n-=1
if digits[0] == 0:
digit = [1]
digit.extend(digits)
digits = digit
return digits

方法二[参考的]

链接→

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
flag = 1
for i in range(len(digits)-1, -1, -1):
digits[i] = (digits[i] + 1) % 10
if digits[i]:
flag = 0
break
if flag:
digits.insert(0,1)
return(digits)

在方法二中使用了range()函数,其用法在此复习一下。

1
2
3
4
5
6
>>> range(1,5) #代表从1到5(不包含5)
[1, 2, 3, 4]
>>> range(1,5,2) #代表从1到5,间隔2(不包含5)
[1, 3]
>>> range(5) #代表从0到5(不包含5)
[0, 1, 2, 3, 4]

Reference

Plus One - LeetCode

LeetCode 题解一(python版)

LeetCode : Plus One #66 - Github