LeetCode 202 快乐数：快慢指针判环解法

LeetCode 202 快乐数：快慢指针判环解法

在数学的奇妙花园里，有一种特殊的数字被赋予了'快乐'的称号。快乐数（Happy Number）就像一位在数字迷宫中寻找出口的旅人，它遵循着特定的变换规则，一步步走向最终的归宿——1。

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

让我们以 19 为例，展开这段数字的奇妙旅程：

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

瞧！经过 4 步变换，19 最终到达了幸福的终点——1，因此它是一个快乐数。

解题思路：从数字到链表的思维转换

链表思维的巧妙应用

虽然表面上我们处理的是数字，但如果我们把每个数字看作链表中的一个节点，把数字变换规则看作指向下一个节点的指针，那么快乐数问题就转化为了链表判环问题！

19 → 82 → 68 → 100 → 1 → null

图 1：快乐数的链表表示法。快乐数最终会指向 1，然后结束；不快乐的数则会进入一个循环

快慢指针：龟兔赛跑的智慧

在链表判环问题中，快慢指针算法是一种经典且高效的解决方案。我们可以让两个指针以不同的速度遍历这个'数字链表'：

• 慢指针（p）：每次计算一次数字变换
• 快指针（q）：每次计算两次数字变换

如果存在环（即数字不快乐），快慢指针终将相遇；如果数字快乐，快指针会率先到达 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); // 快指针先走一步
    
    
     (fast !=  && slow != fast) {
        slow = (slow); 
        fast = ((fast)); 
    }
     fast == ; 
}