题解 | 快乐数-Java
快乐数
https://www.nowcoder.com/practice/293b9ddd48444fa493dd17da0feb192d
时间复杂度 | 空间复杂度 | 特点 | |
解法1：哈希集合 | O(log n) | O(log n) | 直观易懂，需额外存储空间 |
解法2：快慢指针 | O(log n) | O(1) | 最优解，无额外空间 |
解法1：HashSet检测循环
import java.util.*;
public class Solution {
// 计算一个数的各位数字平方和
private static int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n = n / 10;
}
return sum;
}
public boolean happynum (int n) {
Set<Integer> seen = new HashSet<>();
// 若n为1则是快乐数；若n重复出现则进入循环（非快乐数）
while (n != 1 && !seen.contains(n)) {
seen.add(n); // 记录已出现的数
n = getNext(n); // 计算下一个平方和
}
// 循环结束后，若n为1则是快乐数
return n == 1;
}
}
解法2：快慢指针检测循环
import java.util.*;
public class Solution {
// 计算一个数的各位数字平方和
private static int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n = n / 10;
}
return sum;
}
public boolean happynum (int n) {
int slow = n;
int fast = getNext(n); // 快指针先前进一步
// 若快指针到达1，则是快乐数；若快慢指针相遇，则进入循环（非快乐数）
while (fast != 1 && slow != fast) {
slow = getNext(slow); // 慢指针走1步
fast = getNext(getNext(fast)); // 快指针走2步
}
// 若快指针为1，则是快乐数
return fast == 1;
}
}
