leetcode258题-C语言版-Python版

2016-12-02 12:52:03来源:网络收集作者:程序猿人点击

258. Add Digits



Given a non-negative integernum, repeatedly add all its digits until the result has only
one digit.



For example:



Givennum = 38, the process is like:3
+ 8 = 11,1 + 1 = 2. Since2has
only one digit, return it.



Follow up:

Could you do it without any loop/recursion in O(1) runtime?



258.加数字



给你一个非负整数num,重复把他的各位数字相加直到最后的结果只有一位数字。



例如:



给定num=38,这个过程就像:3+8=11, 1+1=2. 因为2只有一个数字,就返回他。



进一步的:



你能不用任何的循环和递归并且在O(1)的时间复杂度中完成吗?



思路:对于任意整数abcde...,对其某一位i,如果将i抽离出来视作个位数,抛弃了他的权重,这个过程是可以分解成重复减9的行为的。例如14,对十位数1来说,原先表示的是10,抽离出来后表示为1,这个过程是减9。那么34就可以看成3次减9。那么345呢?百位的3先抽离到十位,是减9的重复,再抽离到个位,也是减9的重复。所以总的来说,模9就是题目所述的操作的简化。不太一样的是,模9得到的结果是0-8,而题目中除0以外任何数经题目操作后得到的结果应该是1-9.所以如果模9后得到的是0那么应该改为9.




int addDigits(int num) {
if (num==0) return 0;
int i = num%9;
return i==0?9:i;
}
class Solution(object):
def addDigits(self, num):
"""
:type num: int
:rtype: int
"""
if num == 0:return 0
i = num % 9
return i if i != 0 else 9

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台