LeetCode-258. 各位相加【数学 数论 模拟】
- 题目描述：
- 解题思路一：循环
- 解题思路二：进阶 O(1)
- 解题思路三：
题目描述：
给定一个非负整数 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) 时间复杂度内解决这个问题吗？
解题思路一：循环
class Solution:
def addDigits(self, num: int) -> int:
def add_str(s):
n = len(s)
total = 0
for i in range(n):
total += int(s[i])
return total
while num > 9:
num = add_str(str(num))
return num
#
class Solution:
def addDigits(self, num: int) -> int:
while num >= 10:
sum = 0
while num:
sum += num % 10
num //= 10
num = sum
return num
时间复杂度：O(n)
空间复杂度：O(1)
解题思路二：进阶 O(1)
该方法的目的是计算一个整数 num 的数位根，即反复相加其各位数字直到得到一个单位数的过程。这是一个数学特性，任何非零整数的数位，如果反复相加，最终会得到一个数，该数除以9的余数与原数除以9的余数相同。如果数字是0，其数位根就是0。
O(1) 数学推理：设某个数字的字符串表示为’abc’，则这个数字代表a100 + b10 + c，转换后成为a + b + c，可见每次转换相当于把原数字减去a99 + b9 = 9 * (a*11 + b)，可以推出只要高于个位的位置上有数字，算法就会减去一个小于原数字的9的倍数，这就相当于数字 % 9。但9 % 9 = 0，而 9 本身就没有十位，因此需要考虑原数字是 0 或 9 的倍数的特殊情况
class Solution:
def addDigits(self, num: int) -> int:
return num % 9 or 9 * bool(num) # 如果num % 9==0，则跳到第二个选项，如歌num == 0返回0，否则返回9
时间复杂度：O(1)
空间复杂度：O(1)
解题思路三：
class Solution:
def addDigits(self, num: int) -> int:
return (num - 1) % 9 + 1 if num else 0
时间复杂度：O(1)
空间复杂度：O(1)
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠
