python(leetcode)-66加一问题

2019-02-17 01:52:38来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

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

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

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

 看到题目觉得非常简单 只需要找到list的最后一个下标位置使其加一 即可。

然而天真如我 下面情况才是这题的重点

输入: [9,9,9]
输出: [1,0,0,0]
解释: 输入数组表示数字 999。

 需要考虑进位的情况

重新思考:

笔者想到的是先将数组数字转为十进制数字,然后加一,接着按位取模得到每一位的值。

上代码(花费时间48ms)击败70%

 1 import math
 2 class Solution:
 3     def plusOne(self, digits):
 4         """
 5         :type digits: List[int]
 6         :rtype: List[int]
 7         """
 8         a=1
 9         num=0
10         lens=len(digits)
11         for i in range(lens-1,-1,-1):
12             num=num+digits[i]*a
13             a=a*10                     #获得list的十进制数字
14         num=num+1
15 
16         bytes=int(math.log10(num))     #计算数字的位数
17         lens_new=bytes+1
18         result=[]
19 
20         for i in range(lens_new):
21             single=int(num/(10**(bytes-i))) #得到每一位的数字
22             result.append(single)
23             num=num-single*10**(bytes-i)    #将得到的位数减去
24         return result
25 
26 if __name__=="__main__":
27     s=Solution()
28     a=[9,9,9]
29     print(s.plusOne(a))

然后举出比较正常的方法

思路:对每个值遍历判断,如果为9则变为0,并且继续遍历,如果为0到8则加1操作,并且break退出判断

上代码(用时44ms)击败98%

 1 class Solution:
 2     def plusOne(self,digits):
 3         """
 4         :param digits:List[int]
 5         :return:List[int]
 6         """
 7         #
 8         for i in range(1,len(digits)+1): #对每一个值遍历
 9             if(digits[-i]==9):   #如果为9则变为0
10                 digits[-i]=0
11             else:                #如果加1则退出
12                 digits[-i]+=1
13                 break
14         if(digits[0]==0):        #如果全都是9那么第一位为1后面加一个0
15             digits[0]=1          #eg:[9,9,9] --> [1,0,0,0]
16             digits.append(0)
17         return digits
18 if __name__=="__main__":
19     s=Solution()
20     a=[5,9,8]
21     print(s.plusOne(a))

 


原文链接:https://www.cnblogs.com/bob-jianfeng/p/10371556.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:基于django的视频点播网站开发

下一篇:python 简单爬取今日头条热点新闻(一)