### 题目描述 给定一个非负整数**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) 时间复杂度内解决这个问题吗？ ### 题目解答 #### 思路 **模拟法** 如果数字大于9在一位数以上，那么反复将各个数位的数相加，直至其变成1位数返回即可。 ```python while num > 9: tmp = 0 while num > 0: tmp += num % 10 num = num // 10 num = tmp return num ``` **复杂度分析** 时间复杂度：$$o(log_{num})$$ 计算一次各位相加的最大可能结果是**82**，对于任意两位数最多只需要计算两次各位相加的结果即可得到一位数。 空间复杂度：$$o(1)$$ **数学法** 可以证明，原数字与其所有数位的数字相加求和之后%9同余数。 ```python class Solution: def addDigits(self, num: int) -> int: if num == 0: return 0 if num % 9 == 0: return 9 return num % 9 ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复