快乐数
难度:
标签:
题目描述
编写一个算法来判断一个数 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 <= 231 - 1
代码结果
运行时间: 19 ms, 内存: 16.1 MB
/*
* The algorithm checks if a number is a happy number using Java Streams.
* A happy number is a number where the sum of the squares of its digits eventually equals 1.
* We use a HashSet to detect loops by storing numbers we've seen before. If we see a number twice,
* it means we're in a loop and the number is not happy.
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;
public class HappyNumberStream {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = Stream.of(String.valueOf(n).split(""))
.mapToInt(Integer::parseInt)
.map(x -> x * x)
.sum();
}
return n == 1;
}
}解释
方法:
该题解的思路是利用哈希集合检测循环。从给定的整数 n 开始，不断计算每一位上的平方和替换 n，直到 n 为 1 或者出现了之前计算过的 n，表示进入了循环。如果最后 n 等于 1，则是快乐数，否则不是。
时间复杂度:
O(logn * loglogn)
空间复杂度:
O(logn)
代码细节讲解
🦆
算法中使用列表记录出现过的数字，为何不使用哈希集合以提高查找效率？
▷🦆
代码中提到如果 n 最终等于 1 则返回 true，但是在循环中是如何确保这个过程最终会停止而不是无限循环？
▷🦆
在函数 `getSum` 中，你用除以 10 和取余操作来处理数字，这种操作对于处理非常大的数字是否仍然有效？
▷相关问题
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？