快乐数
# 📃 题目描述
题目链接:202. 快乐数 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回 false 。
示例 1:
输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2
输出:false
# 🔔 解题思路
⭐ 解题的关键其实就一句话:如果某个结果重复出现过,那这个数就不可能是快乐数,因为既然它曾经出现过,现在出现过,那就代表它未来还会出现,这就是死循环,永远不可能收敛为 1,直接返回 false 即可。
那如何快速判断一个元素是否出现过?我们应该立马就想到哈希。显然这题是不需要用到 HashTable 的 key-value 键值对的,只需要使用 HashSet 存储下结果就行:
class Solution {
public boolean isHappy(int n) {
if (n <= 0) {
return false;
}
Set<Integer> set = new HashSet<>();
int sumOfSquares = 0;
while (n != 1) {
sumOfSquares = getSumOfSquares(n);
// 如果这个sumOfSquares曾经出现过,说明已经陷入了无限循环了,立刻 return false
if (set.contains(sumOfSquares)) {
return false;
}
set.add(sumOfSquares);
n = sumOfSquares;
}
return true;
}
/**
* 获取 n 所有数字的平方和
*/
private static int getSumOfSquares(int n) {
int res = 0;
while (n > 0) {
// n 的最后一个数字
int temp = n % 10;
// 每个数字的平方和
res += temp * temp;
// 从后往前处理
n = n / 10;
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:while (n != 1) 可以看作对这个 n 中出现的所有平方和进行遍历,其时间复杂度为 O(N),然后,while 循环里面的 getSumOfSquares 方法,对一个数进行处理获取到它所有数字的平方和,时间复杂度为 O(N),所以总的时间复杂度为 O(N^2)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10