0202. Happy Number¶
题目信息¶
- 题号:
快乐数
- 难度:
Easy
- 主题:
数学、哈希表、双指针、函数图
- 原题:
- 重点:
把各位平方和看成确定后继,先检测重复状态,再用快慢指针删除历史集合
题目重述¶
给定正整数 n。把当前数的每个十进制数字平方后求和,用这个和替换当前数并持续重复:若
过程最终到达 1,返回 true;若它进入一个不包含 1 的循环,返回 false。
输入满足 1 <= n <= 2^31 - 1。数字 0 的平方贡献是 0;题目只要求判断初始数是否
快乐,不要求保留或返回完整变换序列。
自建示例¶
快乐数会进入 1 这个不动点:
输入:n = 19
序列:19 -> 82 -> 68 -> 100 -> 1
输出:true
非快乐数并非停在某个错误值,而是重复已有状态:
输入:n = 2
序列:2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> ...
输出:false
最小成功状态本身已经是终点:
输入:n = 1
输出:true
C++ 实现¶
#include <unordered_set>
class Solution {
public:
bool isHappy(int n) {
return floydCycle(n);
}
private:
static int nextValue(int value) {
int sum = 0;
while (value > 0) {
int digit = value % 10;
sum += digit * digit;
value /= 10;
}
return sum;
}
bool seenStates(int n) {
std::unordered_set<int> seen;
while (n != 1 && seen.insert(n).second) {
n = nextValue(n);
}
return n == 1;
}
bool floydCycle(int n) {
int slow = n;
int fast = nextValue(n);
while (fast != 1 && slow != fast) {
slow = nextValue(slow);
fast = nextValue(nextValue(fast));
}
return fast == 1;
}
};
题解¶
不断代入为何还不是完整算法¶
最直观的过程就是反复计算当前数的各位平方和,直到当前值变成 1。对于 19,这条路径确实
顺利结束;但对于 2,它会回到 4 后重复整段序列。若代码只有“while (n != 1)”,非快乐数
永远不会退出。
因此原始搜索对象不是一条必然收敛的数列,而是一条沿确定规则前进的状态路径。设
nextValue(x) 为各位平方和,每个正整数恰好只有一个后继 nextValue(x)。一旦再次到达
相同状态,之后的后继也完全相同,路径必然进入环;问题转化为“先到达状态 1,还是先发现重复
状态”。
有限状态让重复必然出现¶
初始 n 最多有 10 位,每位平方最多为 81,所以第一次变换至多得到 10 * 81 = 810。
之后状态至多三位,下一次及后续每次变换至多为 3 * 81 = 243。也就是说,除初始输入外,
路径始终落在一个很小的有限正整数集合中。
有限集合中沿唯一后继不断前进,若没有到达 1,就必然有状态重复。这个上界不是为了硬编码
非快乐环,而是说明“记录重复”与“快慢指针追赶”都会在有限步内结束。
哈希集合先把循环变得可见¶
seenStates 维护已经作为当前状态处理过的整数。每轮先执行 seen.insert(n):若插入成功,
说明 n 首次出现,可以安全地计算下一个状态;若插入失败,说明当前 n 以前出现过,
确定后继会让后续路径完全重复,应返回 false。若 n 先变成 1,循环在插入前结束并
返回 true。
这个方案直接消除了“不知道何时停止”的问题,但把整条已走路径保存在 unordered_set 中。它
是理解状态重复最透明的正确解,却没有利用“每个状态只有一个后继”这一额外结构。
快慢指针删除已见状态¶
每个状态只有一条出边,这条路径与单链表一样,最终是“链尾到 1”或“进入环”。Floyd 判环让
slow 每轮走一步,fast 每轮走两步。若路径进入非 1 环,快指针会在环中追上慢指针;
若路径通向 1,fast 会先到达 1。
初始化 slow = n、fast = nextValue(n)。完成 round 次循环体后,slow 位于从
n 出发的第 round 个后继,fast 位于第 2 * round + 1 个后继。每轮分别应用
一次与两次 nextValue,这个状态关系自然保持。
循环条件先检查 fast != 1。1 本身也是一个长度为 1 的环,但它表示快乐;只有在
fast 不是 1 时与 slow 相遇,才说明进入了不包含 1 的循环。主解选择 Floyd,因为它
在保留相同终止判断的同时删除了哈希集合。
状态走读¶
对 n = 19,两个指针的更新顺序如下:
阶段 |
slow |
fast |
说明 |
|---|---|---|---|
初始化 |
19 |
82 |
fast 先走一步 |
第 1 轮后 |
82 |
100 |
fast 本轮连走两步 |
第 2 轮后 |
68 |
1 |
下一次条件检查返回 true |
对 n = 2,快指针进入环后相对慢指针每轮多走一步:
阶段 |
slow |
fast |
|---|---|---|
初始化 |
2 |
4 |
第 1 轮后 |
4 |
37 |
第 2 轮后 |
16 |
89 |
第 3 轮后 |
37 |
42 |
第 7 轮后 |
42 |
42 |
相遇值不是 1,所以主循环结束后返回 false。这里相遇并不意味着成功;它只证明两条
不同速度的路径已落入同一个非快乐环。
代码分析¶
nextValue 的 value 始终是尚未处理的高位前缀,sum 是已移除低位的平方和。每轮用
% 10 取出一个最低位并累加其平方,再用 / 10 删除该位;循环结束时每个十进制数字
恰好贡献一次。
seenStates 中“先插入、再转移”的顺序使集合准确代表已经处理过的当前状态;若先转移再
记录,会把重复状态的边界与当前值混在一起。floydCycle 则不记录历史,只保持两个位置和
速度差;其 fast = nextValue(nextValue(fast)) 必须连续执行两次,若只走一步,两指针不会
产生追赶关系。
公共入口明确调用 floydCycle。seenStates 保留在同一 Solution 中,是因为它从
原始的重复检测直觉到常量空间判环有实际认知增量,而不是重复提供同一种实现。
复杂度与边界¶
设到达 1 或首次重复前访问了 S 个状态,每次平方和处理至多 D 个十进制数字。
哈希集合方案的时间为 O(SD),额外空间为 O(S);哈希插入的常数时间是期望意义上的。
Floyd 方案同样在 O(SD) 时间内结束,但只使用 O(1) 额外空间。题目给定 32 位上界时
D <= 10,且第一次变换后状态不超过 810,因此两者的运行时间都有固定上界。
n = 1 时,fast 初始化后也是 1,主循环不执行并返回 true。单次平方和最大为 810,
int 足以保存所有中间值;输入为正整数,所以代码不需要为负号或空数字表示单独分支。