theme: arknights
携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第21天，点击查看活动详情
推荐阅读
- CSDN主页
- GitHub开源地址
- Unity3D插件分享
- 简书地址
- 我的个人博客
- QQ群：1040082875
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“编写一个算法来判断一个数是不是快乐数。”
题目链接：
来源：力扣（LeetCode）
链接： 202. 快乐数 - 力扣（LeetCode）
2、题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
代码语言：javascript复制示例 1：
输入： n = 19
输出： true
解释： 12 92 = 82
82 22 = 68
62 82 = 100
12 02 02 = 1示例 2：
输入： n = 2
输出： false二、解题
1、思路分析
今天的题目是快乐数。
今天你快乐了吗？
题意要求我们判断一个数，是否是快乐数，每一次将该数替换为它每个位置上的数字的平方和，直到该数为1。
那么每个数字饿平方和指向另一个数字，所以是从任意数字进行平方和的迭代操作。
比如说数字7，下一个数字是49（72），然后是97(42 92)，不断重复该过程，直到得到了1，那么这个7就是快乐数：
再举一个例子，116，通过反复平方和得到下一个数字，最终得到58之后就开始循环回到58，所以不可能到达1，因此116不是一个快乐数：
那么这个代码应该怎么实现呢：
- 求数字的平方和
- 根据一系列的数字判断是否进入了循环
判断是否进入循环其实也很简单，使用一个哈希表添加出现的数字，当数字再次出现就说明出现了循环。
2、代码实现
代码参考：
代码语言：javascript复制class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum = d * d;
}
return totalSum;
}
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;
}
}
3、时间复杂度
时间复杂度：O(log n)
时间复杂度：O(243 · 3 log n log log n log log log n)...=O(log n)
空间复杂度：O(log n)
衡量空间复杂度主要是看哈希集中中的数字以及它们有多大的指标。
对于足够大的n，大部分空间将有n本身占用 。
三、总结
快乐的知识点又增加了。
这是一道经典的链表找环的题目。
除了链表找环，更进一步的是 有向图找环。
相比于链表找环，每个点可能指向了多个其他的点。
有向图找环 比较经典的做法就是使用 深度优先搜索，从每个点出发，按有向图去游走，游走的时候记录当前走过的路径。如果在搜索的过程中遇到了曾经走过的路，那么就找到环了。
