0202. Happy Number
==================
题目信息
--------
:题号: 0202. 快乐数
:难度: Easy
:主题: 数学、哈希表、双指针、函数图
:原题: `LeetCode 0202 `_
:重点: 把各位平方和看成确定后继,先检测重复状态,再用快慢指针删除历史集合
题目重述
--------
给定正整数 ``n``。把当前数的每个十进制数字平方后求和,用这个和替换当前数并持续重复:若
过程最终到达 ``1``,返回 ``true``;若它进入一个不包含 ``1`` 的循环,返回 ``false``。
输入满足 ``1 <= n <= 2^31 - 1``。数字 ``0`` 的平方贡献是 ``0``;题目只要求判断初始数是否
快乐,不要求保留或返回完整变换序列。
自建示例
--------
快乐数会进入 ``1`` 这个不动点:
.. code-block:: text
输入:n = 19
序列:19 -> 82 -> 68 -> 100 -> 1
输出:true
非快乐数并非停在某个错误值,而是重复已有状态:
.. code-block:: text
输入:n = 2
序列:2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> ...
输出:false
最小成功状态本身已经是终点:
.. code-block:: text
输入:n = 1
输出:true
C++ 实现
--------
.. code-block:: cpp
#include
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 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``,两个指针的更新顺序如下:
.. list-table::
:header-rows: 1
* - 阶段
- slow
- fast
- 说明
* - 初始化
- 19
- 82
- fast 先走一步
* - 第 1 轮后
- 82
- 100
- fast 本轮连走两步
* - 第 2 轮后
- 68
- 1
- 下一次条件检查返回 true
对 ``n = 2``,快指针进入环后相对慢指针每轮多走一步:
.. list-table::
:header-rows: 1
* - 阶段
- 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`` 足以保存所有中间值;输入为正整数,所以代码不需要为负号或空数字表示单独分支。