Leetcode 每日一题 202.快乐数

题意

算法思路

过题图片

算法实现

代码解析

复杂度分析

题目链接

结论

题意

判断正整数 n 是不是快乐数。

快乐数定义：

（1）每次将正整数替换为它每个位置上的数字的平方和。

（2）重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。

（3）如果可以变为 1，这个数就是快乐数。

示例
输入：19

输出：true

解释：

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

提示
1 <= n <= 2^31 -1

算法思路

这个问题的关键在于处理可能的无限循环。如果一个数最终会进入一个循环，那么它肯定不是快乐数。因此，我们可以使用哈希集合来记录在迭代过程中出现过的数。如果新生成的数已经在哈希集合中，那么我们可以确定这个数不是快乐数，因为它已经进入了循环。

过题图片

算法实现

以下是使用Java语言实现的算法：

import java.util.Set;
import java.util.HashSet;

class Solution {
    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
    
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
}

代码解析

getNextNumber 方法：这个方法用于计算给定数的下一个数，即每个位置上的数字的平方和。它通过不断取模和除法操作来实现。
isHappy 方法：这是主要的算法实现。我们使用一个哈希集合 record 来记录出现过的数。在循环中，我们不断计算下一个数，并检查这个数是否已经在 record 中。如果已经在 record 中，说明进入了循环，返回 false。如果计算得到的数为1，说明找到了快乐数，返回 true。

复杂度分析

时间复杂度：最坏情况下，我们需要遍历所有可能的数直到找到1或者确定循环。在最坏情况下，这个算法的时间复杂度是 O(k)，其中 k 是快乐数序列的长度。对于非快乐数，时间复杂度取决于循环的长度，但在实际应用中，这个循环通常不会太长。
空间复杂度：我们使用了一个哈希集合来存储已经出现过的数，因此空间复杂度是 O(k)，其中 k 是不同数的数量。