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`` 足以保存所有中间值;输入为正整数,所以代码不需要为负号或空数字表示单独分支。