LeetCode 202 快乐数：快慢指针解法详解

快乐数的定义

快乐数（Happy Number）是一个有趣的数学概念。对于一个正整数，如果将其各位数字的平方和不断进行替换，最终能够得到 1，那么这个数就被称为快乐数。反之，如果陷入一个不包含 1 的循环，那么这个数就是不快乐的。

以 19 为例：

19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1

经过 4 步变换，19 到达了终点 1，因此它是快乐数。

解题思路：链表思维转换

虽然处理的是数字，但我们可以把每个数字看作链表中的一个节点，变换规则看作指向下一个节点的指针。这样，快乐数问题就转化为了经典的链表判环问题。

如果不快乐，数字序列会进入循环；如果快乐，序列最终指向 1 并结束。

快慢指针策略

在链表判环中，快慢指针（Floyd's Cycle Detection）是高效且节省空间的方案。

• 慢指针（slow）：每次走一步（一次变换）。
• 快指针（fast）：每次走两步（两次变换）。

如果存在环，快慢指针终将相遇；如果数字快乐，快指针会率先到达 1。

算法实现：C++ 代码解析

核心逻辑

我们需要两个函数：一个是计算数字变换的辅助函数，另一个是主判断逻辑。

// 计算数字 n 的下一个变换结果
int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10; // 获取最后一位数字
        sum += digit * digit;
        n /= 10; // 去掉最后一位数字
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = getNext(n); // 快指针先走一步

    // 当快慢指针不相等且快指针未到达 1 时继续循环
    while (fast != 1 && slow != fast) {
        slow = getNext(slow); // 慢指针走一步
        fast = getNext(getNext(fast)); 
    }
     fast == ; 
}