LeetCode 258. 各位相加
题目描述
题意分析
对非负整数反复求十进制数位和，直到只剩一位，返回最终结果。进阶要求不使用循环或递归，在常数时间内完成。
这个最终的一位数称为数字根。求它不必知道每一轮的具体数值，只需找出每轮求和都不改变的性质。
解法：数字根公式
核心思路
[!blue]
一个十进制整数由各位数字乘上
1、10、100……后相加得到。这些权重除以 9 的余数都是 1，所以原数与它的数位和除以 9 的余数相同。无论重复求和多少次，模 9 的余数始终保持不变。对正整数来说，数位和始终为正；只要当前数至少有两位，数位和就严格小于它，最终一定停在
1...9。这个范围中的九个数字恰好代表模 9 的九种余数，因此余数已经唯一确定最终结果。余数为
1...8时直接对应同一个数字，正数余数为 0 时应对应 9。用1 + (num - 1) % 9就能把结果统一映射到1...9，避免把正的 9 的倍数误算成 0。输入 0 不属于上面的正整数情况，它的数位和仍为 0，直接返回 0。其余输入使用公式，就满足不循环、不递归的进阶要求。
解题步骤
- 如果
num == 0，返回 0。- 对正整数计算
(num - 1) % 9，得到0...8范围的余数。- 将余数加一，返回对应的
1...9数字根。
代码实现
class Solution {
public int addDigits(int num) {
// 正数用一到九代表模九余数，九的倍数对应九。
return num == 0 ? 0 : 1 + (num - 1) % 9;
}
}
func addDigits(num int) int {
if num == 0 {
return 0
}
// 正数用一到九代表模九余数，九的倍数对应九。
return 1 + (num-1)%9
}
复杂度分析
- 时间复杂度：$O(1)$，只进行固定次数的判断和整数算术运算。
- 空间复杂度：$O(1)$，不需要额外数据结构。
关键点总结
[!green]
- 每轮数位和都保持模 9 的余数，最终结果由这个不变量确定。
- 正数的数字根在
1...9，余数 0 对应 9。- 输入 0 单独返回 0，其他输入统一套用公式。
易错点总结
[!yellow]
- 直接返回
num % 9：会把正的 9 的倍数错误地映射为 0。- 把所有余数为 0 的输入都返回 9：输入 0 的正确结果仍然是 0。
- 对 10 取模：只能得到当前个位，不能表示多轮数位和的结果。
- 只做一次数位求和：一次求和后仍可能是多位数，公式求的是最终的一位结果。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！