LeetCode 202. 快乐数
题目描述
✅ 202. 快乐数
题意分析
从正整数
n出发，反复把当前数替换为十进制各位数字的平方和。能到达 1 就是快乐数；若进入不含 1 的循环，以后也不可能到达 1。
解法：快慢指针检测循环
核心思路
[!blue]
记一次变换为
f(x)。每个数的下一状态唯一，因此可以把数看作链表节点，把f(x)看作它的next。相同的数再次出现后，之后的整段过程也会重复。还需要说明过程为什么一定停止在 1 或进入环。题目中的
n最多有 10 位，第一次变换不超过10 × 81 = 810；之后至多有 3 位，下一次变换不超过 243。后续状态都留在这个有限范围内，所以不可能永远出现新数。又因为f(1) = 1，到达 1 也可以看作进入了一个自环。用 Floyd 快慢指针判断进入的是哪种环：
slow每轮变换一次，fast每轮变换两次。两者都进入环后，快指针每轮相对慢指针多前进一步，距离按环长取模，必然相遇，不必保存所有历史状态。初始化
slow = n、fast = f(n)，先错开一步。循环中只要fast == 1就已确认快乐；若两者在非 1 的位置相遇，说明进入了不含 1 的环，返回失败。
解题步骤
- 实现
getNext：反复取个位，累加平方，再去掉个位。- 初始化慢指针为
n，快指针为getNext(n)。- 当快指针尚未到 1 且两指针未相遇时，慢指针走一步，快指针走两步。
- 退出后返回
fast == 1。输入本来就是 1 时，初始化后
fast也为 1，直接返回成功。快指针途中经过 1 也不会跳过答案，因为下一次变换仍然是 1；此时慢指针不一定已经到达 1。
代码实现
class Solution {
public boolean isHappy(int n) {
int slow = n;
// 先错开一步，避免尚未移动就因两个指针相等而退出。
int fast = getNext(n);
while (fast != 1 && slow != fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}
private int getNext(int num) {
int sum = 0;
while (num > 0) {
int digit = num % 10;
// 状态转移只依赖各位平方和，重复状态代表进入循环。
sum += digit * digit;
num /= 10;
}
return sum;
}
}
func isHappy(n int) bool {
slow := n
// 先错开一步，避免尚未移动就因两个指针相等而退出。
fast := getHappyNext(n)
for fast != 1 && slow != fast {
slow = getHappyNext(slow)
fast = getHappyNext(getHappyNext(fast))
}
return fast == 1
}
func getHappyNext(num int) int {
sum := 0
for num > 0 {
digit := num % 10
// 状态转移只依赖各位平方和，重复状态代表进入循环。
sum += digit * digit
num /= 10
}
return sum
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$。对初始数取各位需要扫描其十进制位；在题目的整数范围内，后续状态及进入环、相遇所需的步数都有固定上界。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 唯一后继保证重复状态之后的过程完全相同，有限状态保证最终一定重复。
- 快慢指针的速度差保证它们在环内相遇，省去了保存历史数值的集合。
- 1 本身是自环；到达 1 判成功，在其他位置相遇判失败。
易错点总结
[!yellow]
- 把整个数平方，而不是逐位平方求和，会从第一步就改变状态链。
- 当前代码在移动前判断是否相遇，若都初始化为
n，会在尚未开始变换时直接退出。- 快指针也只走一步时，两者在环中的间距不会变化，无法保证相遇。
- 循环以快指针到达 1 为成功条件，返回时也应检查
fast == 1，不能要求慢指针同时到达。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 141. 环形链表 | 简单 | 把每次数字变换看作next边，快慢指针同样能判断是否进入循环。 |
| 142. 环形链表 II | 中等 | 用快慢指针确定环或中间位置；本题将数字变换视为隐式后继关系，该题在相遇后推导环入口。 |
| 287. 寻找重复数 | 中等 | 用快慢指针确定环或中间位置；本题将数字变换视为隐式后继关系，该题将数组值视为后继指针寻找重复入口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！