各位相加leetcode解题

各位相加 Add Digits 题述

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38

输出: 2

解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶:

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

解题思路及代码

思路一 使用循环解题 ：使用循环或递归来解决这个问题是很简单的，只需要 把 输入的非负整数 转变成 字符串

然后 每个字符 取出来 再以 int类型相加 ，

判断加和后的位数，如果不是一位，

再循环一次上面做的事情。这个代码就懒得写了。。

思路二 不使用循环解题 ： 此时就需要找数据之间的关系了，

假设我们有个4位数， 1314， 1314= 11000+3100+110+41

换个形式写 就是 1000 a +100 b +10 c + d

我们要求的是 a + b + c+d

这其中的关系就 比较明显了 ， 他们相差 999a + 99 b + 9c

3位数： 100 a + 10 b +c

我们要求的是： a + b +c

相差 99 a + 9 b

2位数： 10a+b

要求的是 a+b

相差 9a

1位数： a

要求： a

相差： 0

由此可得一个规律，两位数以上，输入的非负整数 对 它的位数-1个9 求余 可初步得到我们要求的数。

因为我们不仅仅是要简单地把数的 各个位数相加 我们还要一直加，加到结果只是 一位数。

很明显 十以内的数字就是它本身了，但 像 999 或者 998 之类的数字，我们还要接着再运算，

像 999 这种 可以整除 9 的数属于特例， 它的结果肯定是9 ，所以不妨在一开始就将这类数分类处理，

像998 这样的数，在经过对 99 求余之后 ，所剩的数也不会超过两位了，

所以接下来还要对 9 求余数，就可得一位数的解了。

所以，代码思路就是：

输入非负整数num，

先判断，如果 num 大于等于 10：

如果 num 能整除 9

返回 9

如果不能：

就除以 num 最高位数-1 个 9 求其余数

如果余数大于十：

再除一次9

如果余数不大于10：

返回 余数

如果 num 不大于 10：

返回 num

class Solution:
def addDigits(self, num: int) -> int:
if num >=10:
if num%9==0:
return 9
else:
str1 = str(num)
lenth9 = len(str1) - 1
str2 = '9' * lenth9
int9 = int(str2)
res = num % (int9)
if res>=10:
return (res%9)
else:
return res
else:
return num


附图：