LeetCode 202. 快乐数

2025-05-21 HGNULB 约 5 分钟

文章信息 12 个分类 4 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动美团阿里巴巴快手腾讯华为面试经典 150 题

题目描述

✅ 202. 快乐数

题意分析

给定一个正整数 n，对它反复执行同一个操作：把各个数位上的数字分别平方后求和，用结果替换原数。如果这个过程最终变成 1，就称 n 是快乐数，返回 true；否则返回 false。

题面里有一句话是整道题的题眼：「如果这个过程结果为 1，那么这个数就是快乐数；否则它会无限循环但始终变不到 1」。这等于直接告诉你，非快乐数不会发散到无穷，也不会永远产生新值，而是必定进入一个不含 1 的循环。所以判定的实质是：这条状态链是撞上 1，还是撞上一个环。

为什么一定会进入循环？因为这个变换会把大数迅速压小。任何三位数经过一次变换最多得到 $9^2 \times 3 = 243$；更一般地，一个 d 位数的结果不超过 $81d$，而当 d >= 4 时 $81d < 10^{d-1}$，位数必然减少。所以不管起点多大，几步之内就会落入 [1, 243] 这个有限状态集合里。有限集合上无限地走下去，鸽巢原理保证状态必然重复，也就是必然成环。

变换还有一个重要性质：next(x) 只由 x 决定，是一个确定的一元函数，每个状态出度恰好为 1。这意味着状态图长得和单链表一模一样——一条尾巴接一个环。既然结构等价于链表，链表判环那套工具就可以整个搬过来。

边界方面，n 本身可能就是 1，此时应直接返回 true；n 是正整数所以不必处理 0 和负数；1 的后继仍是 1，可以看成一个自环，恰好让「到达 1」这件事在链表视角下自然成立。

解法：快慢指针检测循环

核心思路

令 next(x) 为各位数字平方和。每个状态只有唯一后继，因此状态序列与链表相同：要么进入 1 的自环，要么进入一个不含 1 的环。

使用 Floyd 判圈：慢指针每轮执行一次 next，快指针执行两次。若存在环，两者进入环后相对距离每轮改变一步，最终必然相遇；若序列到达 1，快指针会停在 1 的自环中。

初始化 slow = n、fast = next(n)，避免初始相等导致误退出。循环结束时，fast == 1 表示快乐数，否则两指针是在非 1 环中相遇。相比记录已访问状态的集合，Floyd 将额外空间降为 $O(1)$。

解题步骤

实现 getNext：反复取个位，累加平方，再去掉个位。

初始化慢指针为 n，快指针为 getNext(n)。

当快指针尚未到 1 且两指针未相遇时，慢指针走一步，快指针走两步。

退出后返回 fast == 1。

19 → 82 → 68 → 100 → 1，所以返回 true；2 会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的环，所以返回 false。

代码实现

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)$。首次变换扫描全部十进制位，之后状态迅速落入有常数上界的有限集合。

空间复杂度：$O(1)$。

关键点总结

确定的一元状态转移会形成「链 + 环」，因此可直接套用 Floyd 判圈。

任意 d 位数的下一状态不超过 $81d$，状态最终进入有限范围，所以非快乐数一定成环。

1 本身是自环；退出后检查快指针，慢指针此时未必已经到 1。

哈希集合写法更直观，Floyd 的优势是常数额外空间。

易错点总结

把整个数平方，而不是逐位平方求和，会从第一步就改变状态链。

将快慢指针都初始化为 n，会因初始相等而直接退出。

快指针只走一步时速度相同，无法保证发现环。

返回 slow == 1 会漏掉快指针先到 1 的情况，例如 19。

相似题目

题目	难度	考察点
141. 环形链表	简单	判断链表中是否存在环
142. 环形链表 II	中等	相遇后再定位环的入口节点
287. 寻找重复数	中等	把数组下标映射建模成链表判环
457. 环形数组是否存在循环	中等	带方向约束的环检测
面试题 02.08. 环路检测	中等	Floyd 判圈的数学推导
LCR 022. 环形链表 II	中等	双指针与哈希两种解法对照