题目描述:
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
Hint:
A naive implementation of the above process is trivial. Could you come up with other methods?
What are all the possible results?
How do they occur, periodically or randomly?
题目大意:
给定一个非负整数num,重复地将其每位数字相加,直到结果只有一位数为止。
例如:
给定 num = 38,过程像这样:3 + 8 = 11, 1 + 1 = 2。因为2只有一位,返回之。
进一步思考:
你可以不用循环,在O(1)运行时间内完成题目吗?
提示:
一个直观的解法就是模拟上述过程。你可以想到别的方法吗?
结果一共有多少种可能性?
它们是周期性出现的还是随机出现的?
解题思路:
方法I:按照题目要求使用循环模拟演算过程
Python代码:
class Solution:
# @param {integer} num
# @return {integer}
def addDigits(self, num):
while num > 9:
c = 0
while num:
c += num % 10
num /= 10
num = c
return num
方法II:观察法
根据提示,由于结果只有一位数,因此其可能的数字为0 - 9
使用方法I的代码循环输出0 - 19的运行结果:
in out in out 0 0 10 1 1 1 11 2 2 2 12 3 3 3 13 4 4 4 14 5 5 5 15 6 6 6 16 7 7 7 17 8 8 8 18 9 9 9 19 1
可以发现输出与输入的关系为:
out = (in - 1) % 9 + 1
Python代码:
class Solution:
# @param {integer} num
# @return {integer}
def addDigits(self, num):
if num == 0:
return 0
return (num - 1) % 9 + 1
本文链接:http://bookshadow.com/weblog/2015/08/16/leetcode-add-digits/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
zijii 发布于 2015年12月1日 00:07 #
这怎么看出来的啊,太牛逼了
Binggo 发布于 2016年4月30日 17:32 #
对啊,怎么总结出来的
自说自话的菜菜 发布于 2016年6月21日 21:06 #
(num - 1) % 9 + 1
为什么要先减1再加1呢??
直接num % 9不是一样的效果么?
风铃中的刀声 发布于 2017年1月31日 02:51 #
如果直接使用n%9,那么当n=9的话n%9=0。