[NC]391. 快乐数

🚩传送门： 牛客题目
力扣题目

题目

编写一个算法来判断一个数 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 ，也可能是 无限循环 但始终变不到 。
• 如果这个过程 结果为，那么这个数就是快乐数。

如果 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

解题思路：快慢指针

我们可以先举几个例子。我们从 开始。则下一个数字是 （因为 ），然后下一个数字是 （因为 ）。我们可以不断重复该的过程，直到我们得到 。因为我们得到了 ，我们知道数字 是一个快乐数，函数应该返回 true。

再举一个例子，让我们从 开始。通过反复通过平方和计算下一个数字，我们最终得到 ，再继续计算之后，我们又回到 。由于我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到 。所以对于 ，函数应该返回 false。

根据我们的探索，我们猜测会有以下三种可能。

1. 最终会得到 。
2. 最终会进入循环。
3. 值会越来越大，最后接近无穷大。

第三个情况比较难以检测和处理。为什么无限循环就一定是走到了环了呢 ？而不是链表上的数字越变越大 ？

设 ， 表示每一位上的数字，并且 。我们有

我们需要证明：

以下是证明：

因此只有两种结果：

1. 最终会得到 。
2. 最终会进入循环。

对于链表的环问题，经典解法使用快慢指针

复杂度分析

时间复杂度：

空间复杂度：，指针需要常数的额外空间

我的代码

class Solution {
    // 寻找下一个数
    public int bitSquareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int bit = n % 10;
            sum += bit * bit;
            n = n / 10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = bitSquareSum(slow);    // 走1步
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);    // 走2步
        } while (slow != fast);            // 如果有环一定会相交、没环快指针会在1处等待慢指针
        return slow == 1;
    }
}