难度: Easy
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。
示例 1:
输入: num =38输出: 2 解释: 各位相加的过程为： 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 由于2是一位数，所以返回 2。
示例 2:
输入: num = 0 输出: 0
提示：
0 <= num <= 231 - 1
进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？
Submission
运行时间: 20 ms
内存: 16.0 MB
class Solution:
def addDigits(self, num: int) -> int:
s1 = str(num)
len1 = len(s1)
sum = 0
for i in range(len1):
sum += int(s1[i])
# print(i, s1[i], sum)
if sum < 10:
# print("sum---------", sum)
return sum
else:
return self.addDigits(sum)
Explain
这个题解采用了递归的思路。首先将整数转为字符串，然后遍历字符串的每一位，将其转为整数并累加到变量sum中。如果sum小于10，说明已经得到一位数，直接返回sum；否则递归调用addDigits函数，将sum作为新的输入，继续执行各位相加的操作，直到得到一位数为止。
时间复杂度: O(n * logn)
空间复杂度: O(n)
class Solution:
def addDigits(self, num: int) -> int:
s1 = str(num) # 将整数转为字符串
len1 = len(s1) # 获取字符串的长度
sum = 0 # 初始化累加变量
for i in range(len1): # 遍历字符串的每一位
sum += int(s1[i]) # 将字符转为整数并累加到sum中
# print(i, s1[i], sum)
if sum < 10: # 如果sum小于10，说明已经得到一位数
# print("sum---------", sum)
return sum # 直接返回sum
else:
return self.addDigits(sum) # 递归调用addDigits函数，将sum作为新的输入
Explore
递归方法提供了一个直观和简洁的解决方案，允许我们以较少的代码行数实现功能。递归通常在逻辑上更容易理解和实现，特别是对于那些在逻辑上自然递归的问题。在本题中，每次递归调用都是在处理上一步的输出，直到达到结果满足特定条件（即变为一位数），这种自然的递归结构使得代码更易于理解。尽管迭代可能在某些情况下更高效，但递归在这里提供了清晰的逻辑流。
是的，递归方法中如果输入数字非常大，递归深度可能会增加，从而影响性能和消耗更多的栈空间。在极端情况下，过深的递归可能导致栈溢出错误。然而，对于本题而言，由于每次递归调用都大幅度减少数字的位数，递归深度实际上受到位数减少的速度制约，通常不会达到导致栈溢出的层次。
是的，该递归解法考虑了输入为0的情况，直接返回0作为结果，因为0的各位之和仍然是0。至于最大可能值，由于Python的整数类型是动态大小的，理论上可以处理任意大小的整数，递归方法同样适用。每次递归都会将输入的位数减少，最终将达到一位数，因此递归解法可以有效处理从最小到最大可能值的所有输入。
是的，存在通过直接数学运算的方法来处理这个问题，称为数字根或模数运算。可以通过对数字执行模9的操作得到相同的结果，具体方法是：如果一个数是9的倍数且不是0，则各位相加的结果为9；否则，结果为该数模9的余数。这种方法不需要将数字转换为字符串，可以直接通过数学运算得到结果，从而减少了字符串操作的开销，提高了执行效率。