0202. Happy Number

题目信息

题号:
  1. 快乐数

难度:

Easy

主题:

数学、哈希表、双指针、函数图

原题:

LeetCode 0202

重点:

把各位平方和看成确定后继,先检测重复状态,再用快慢指针删除历史集合

题目重述

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