题目描述：

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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码