力扣经典150题第四十四题：快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true；不是，则返回 false。
示例
示例 1:
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2:
输入：n = 2
输出：false
解题思路
使用一个哈希集合来存储已经出现过的数字，避免陷入无限循环。对于每个数字 n，重复计算每个位置上的数字的平方和，并判断是否等于 1。如果等于 1，则说明是快乐数；如果出现重复数字，则说明陷入了循环，不是快乐数。
完整代码
import java.util.HashSet; import java.util.Set; public class HappyNumber { public boolean isHappy(int n) { Set<Integer> seen = new HashSet<>(); while (n != 1 && !seen.contains(n)) { seen.add(n); n = getNext(n); } return n == 1; } private int getNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; } public static void main(String[] args) { HappyNumber solution = new HappyNumber(); int n1 = 19; System.out.println("示例 1 是否是快乐数：" + solution.isHappy(n1)); int n2 = 2; System.out.println("示例 2 是否是快乐数：" + solution.isHappy(n2)); } }
复杂度分析
- 时间复杂度：O(log n)，其中 n 是输入的数字 n。在循环过程中，数字 n 每次变为下一个数字的过程的时间复杂度与 n 的位数相关，即 O(log n)。
- 空间复杂度：O(log n)，哈希集合 seen 存储的元素个数最多为数字 n 的位数。
总结与结语
本题通过模拟数字变换的过程，利用哈希集合来检测循环，判断一个数是否是快乐数。这种解法的时间复杂度为 O(log n)，空间复杂度也为 O(log n)，是一种高效的解决方案。
掌握这种利用哈希集合来避免重复计算的方法，能够更好地解决类似的数学问题，提高编程的技能和效率。
