目录
?
1. 题目描述
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。
示例 1:
输入: num = 38
输出: 2?
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。
示例 2:
输入: num = 0
输出: 0
?
提示：0 <= num <= 2**31?- 1
?
进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题分析
2.1 递归法
????????逐位相加，如果结果小于10就返回；否则就针对结果再执行逐位相加；。。。直到最终得到的结果小于10返回。这是典型的递归法的思路。
?
????????时间复杂度：对于 num 计算一次各位相加需要 的时间。需要几次递归调用能够结束呢。由于0 <= num <= 2**31?- 1=2147483647，所以最大为10位数，且最高位不大于2，所以第一轮各位相加最大可能结果为92，最多还需要两次，所以最大递归调用次数为3次。所以总的时间复杂度仍为
。
????????空间复杂度：O(1)。存储结果的digitsum以及递归调用的开销均为常数。
2.2 数学方法
????????对于给定的自然数，反复将各个位上的数字相加，直到结果为一位数，该一位数被称为原自然数的数根。数根又称数字根（Digital?root），是自然数的一种性质，很显然每个自然数都有唯一一个数根。利用自然数的性质，则能在 O(1) 的时间内计算数根。
? ? ? ? 设num为n位数，从高位到低位的数字分别记为a0, a1,...,a(n-1)，则可以得到：
? ? ? ? 由于(10**i-1)必定是9的倍数，所以，num的各数位之和与num自身是模9同余的，记为：
? ? ? ? 进一步，num_digitsum各数位之和也是与num_digitsum同余的。。。所以，任意自然数num的数根就等于num模9运算的结果？且慢，当num=9时，数根是9而不是0！原因在于要返回的值是10以内，而不是模9运算结果范围的9以内。所以这里还需要进一步的区分讨论，如下所示：
- 当num 不是 9 的倍数时，其数根即为num模9运算结果。
- 当num 是 9?的倍数时：
- ????????如果 num=0，则其数根是 0；
- ????????如果 num>0，则各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。
????????
3. 代码实现
import time
class Solution:
def addDigits(self, num: int) -> int:
# print('addDigits({0})'.format(num))
if num < 10:
return num
else:
digitsum = 0
while num > 0:
digitsum += num%10
num = num // 10
if digitsum < 10:
return digitsum
else:
return self.addDigits(digitsum)
if __name__ == '__main__':
sln = Solution()
num = 38
tStart = time.time()
ans = sln.addDigits(num)
tElapsed = time.time() - tStart
print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(num,ans,tElapsed))?
本系列总目录：
笨牛慢耕的Leetcode解题笔记(动态更新。。。)
https://chenxiaoyuan.blog.csdn.net/article/details/123040889
?