LeetCode 258. 各位相加
目录
题目描述
题意分析
给一个非负整数
num，反复执行「把它的各位数字相加得到新数」这个操作，直到结果只剩一位为止，返回这个一位数。题目进阶要求不用循环或递归、在 $O(1)$ 时间内完成。先确认这个过程一定会停：只要
num有两位以上，各位数字之和一定严格小于num本身（因为 $10a + b > a + b$ 当 $a > 0$），所以数值单调递减且有下界 0，必然收敛到一位数。这保证了题目良定义，也说明朴素模拟是可行的。真正的信号藏在进阶要求里。「不用循环、不用递归、$O(1)$」意味着不能模拟，必须找到一个闭式公式。能有闭式公式，前提是这个反复求数位和的过程存在某个在操作下不变的量——找到它，答案就只是这个不变量的函数。
数据范围是 $0 \le num \le 2^{31} - 1$，全部落在 32 位有符号整数内，所以公式中的中间运算不会溢出，不需要长整型。
边界只有两处，但都关键。
num = 0时它已经是一位数，直接返回 0，且 0 是唯一一个结果为 0 的输入。其余情况结果必落在 1 到 9 之间——因为一位数里只有 0 对应输入 0，正整数不可能收敛到 0（各位数字和为 0 只能是全零）。这条「非零输入的答案范围是 $[1, 9]$」正是后面公式能成立的基础。
解法：数字根公式
核心思路
十进制中 $10^i \equiv 1 \pmod 9$，所以一个数与其各位之和模 9 同余。反复求数位和不会改变这个余数，最终的一位数就是原数的数字根。
对正整数，答案位于 1 到 9。普通余数位于 0 到 8，且 9 的倍数余 0 却应返回 9，因此先平移一位：
digitalRoot(num) = 1 + (num - 1) % 9。0 是唯一例外，按定义直接返回 0。状态不变量是每次数位求和前后模 9 的剩余类相同。
正确性说明：每次变换都保持模 9 同余，最终正数字根又是区间 1 到 9 中该剩余类的唯一代表，因此闭式公式与逐轮计算相同；0 单独处理后覆盖全部输入。
解题步骤
- 若
num == 0，返回 0。- 对正数计算
(num - 1) % 9，把 9 的倍数映射到余数 8。- 加回 1，得到范围 1 到 9 的数字根。
38 → 3+8=11 → 1+1=2，公式同样得到 2。18不能直接返回18 % 9 = 0，数字根应为 9；num = 0则返回 0。
代码实现
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)$。不使用额外容器。
关键点总结
- 数位和保持模 9 同余，这是把迭代压缩成闭式的核心不变量。
- 正数数字根取 1 到 9 中的代表元，因此要“减一取模再加一”。
- 0 不在正数公式的定义域内，必须单独返回 0。
易错点总结
- 直接返回
num % 9：num = 18会返回 0，正确答案是 9。- 使用
num % 9 == 0 ? 9 : num % 9却漏掉 0：num = 0会错误返回 9。- 平移方向写反：
1 + (num + 1) % 9在num = 8时返回 1。- 模数写成 10：它只保留个位，不保持数位和迭代的不变量。
- 模拟时不重置本轮数位和：上一轮结果会被重复累计，状态语义失效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 202. 快乐数 | 简单 | 同样反复求数位函数，但过程会成环而非单调收敛，需要快慢指针或哈希判环 |
| 172. 阶乘后的零 | 中等 | 把计数问题化成「统计因子 5 的个数」，同属找不变量后闭式求解的路子 |
| 263. 丑数 | 简单 | 反复除以 2、3、5 直到不能整除，收敛判定靠因子分解而非同余 |
| 507. 完美数 | 简单 | 因数和判定，重点在只枚举到 $\sqrt{n}$ 并成对累加，边界要排除 1 |
| 728. 自除数 | 简单 | 逐位拆解后做整除校验，考察拆位循环里对数字 0 的短路处理 |
| 191. 位1的个数 | 简单 | 换成二进制下的逐位统计，n & (n-1) 消最低位 1 是对应的 $O(1)$ 级技巧 |
| 357. 统计各位数字都不同的数字个数 | 中等 | 从逐位运算转向逐位组合计数，考察排列数递推而非同余性质 |