快乐数 | LeetCode-203 | 一个简单的数学题！| Floyd判圈算法

不知道Floyd判圈算法这道题做起来一点也不快乐！ 🙋大家好！我是毛毛张!

---

LeetCode链接：202. 快乐数

---

1.题目描述

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

「快乐数」 定义为：

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

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

示例 1：

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

示例 2：

输入：n = 2
输出：false

提示：

• $1 <= n <= 2^{31} - 1$

2.题解

2.1 Floyd判圈算法

class Solution {
    public boolean isHappy(int n) {
        // 使用快慢指针法检测环的存在。快指针每次移动两步，慢指针每次移动一步。
        // 初始时，快指针移动两次后的结果，慢指针移动一次后的结果
        int fast = iterator(iterator(n));
        int slow = iterator(n);
        
        // 快慢指针相遇时，说明存在环
        while (fast != slow) {
            fast = iterator(iterator(fast)); // 快指针移动两次
            slow = iterator(slow);           // 慢指针移动一次
        }

        // 快慢指针相遇后，判断是否在环的入口，即是否为1
        return fast == 1;
    }

    // 辅助方法，用于计算数位平方和
    public int iterator(int n) {
        int sum = 0;
        while (n != 0) {
            int mod = n % 10; // 取出最低位数字
            sum += mod * mod; // 计算该数字的平方并累加到sum
            n = n / 10;       // 去掉最低位数字
        }
        return sum; // 返回累加的平方和
    }
}

2.2 哈希集合

class Solution {
    public boolean isHappy(int n) {
        // 创建一个集合用于存储计算过程中出现过的数字，防止出现无限循环
        Set<Integer> set = new HashSet<>();
        int cur = n;  // 当前需要检查的数字
        
        // 循环进行计算，直到发现一个重复的数字
        while (!set.contains(cur)) {
            set.add(cur);  // 将当前数字加入集合
            cur = iterator(cur);  // 计算当前数字每位的平方和
        }
        
        // 如果循环退出时，cur等于1，说明n是快乐数
        return cur == 1;
    }

    // 计算一个数字每位的平方和
    public int iterator(int n) {
        int sum = 0;
        while (n != 0) {
            int mod = n % 10;  // 取出最低位数字
            sum += mod * mod;  // 计算该数字的平方并累加到sum
            n = n / 10;  // 去掉最低位数字
        }
        return sum;  // 返回累加的平方和
    }
}