202.快乐数

题目:202.快乐数

编写一个算法来判断一个数 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

思路

要判断一个数 n 是否为快乐数，可以使用哈希集合法来检测循环。如果一个数是快乐数，则在若干次变换后会变为 1。如果不是快乐数，它会陷入循环而不会变成 1。

1. **主方法 isHappy**：

   • 使用一个哈希集合 seen 来存储在过程中出现的每一个数字。
   • 在 while 循环中，检查 n 是否等于 1 或者已经在 seen 集合中出现过。如果 n 等于 1，说明 n 是一个快乐数，返回 true。如果 n 已经在 seen 集合中出现过，说明 n 进入了一个循环，不是快乐数，返回 false。
   • 如果 n 既不等于 1，也没有在 seen 集合中出现过，则将 n 加入 seen 集合，并计算 n 的下一个状态。

2. **辅助方法 getNext**：

   • 计算给定数字 n 的每个位置上的数字的平方和。
   • 例如，输入 19，计算结果为 1^2 + 9^2 = 1 + 81 = 82。

• 时间复杂度:O(log₂n)
• 空间复杂度:O(log₂n)

代码

public boolean isHappy(int n) {
    Set<Integer> seens = new HashSet<>();
    // 如果 n 不等于 1 且 getNext(n) 未在 seen 集合中出现过，则继续循环
    while (!seens.contains(getNext(n)) && n != 1) {
        seens.add(n);
        n = getNext(n);
    }
    // 如果 n 等于 1，返回 true；否则返回 false
    return n == 1;
}

// 辅助方法：计算给定数字每个位置上的数字的平方和
private int getNext(int n) {
    int totalNum = 0;
    while (n > 0) {
        int digit = n % 10;
        totalNum += digit * digit;
        n = n / 10;
    }
    return totalNum;
}