202. 快乐数
2024.9.12
题目
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
提示:
1 <= n <= 231 - 1
示例
示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2
输出:false
反思
1.注意C++的语法:
- 函数不能定义在函数中。
return n==1;
可以直接这样判断
2.还是要注意,用int
还是long
3.经过前几题的拷打,本题用哈希集和去做非常合理!利用了值的唯一性
和快速访问
,与128题解2神似!
题解
n在不断循环中,最后会有以下三种可能。
- 最终会得到 1。
- 最终会进入循环。
- 值会越来越大,最后接近无穷大。
但是,可以证明第三种情况并不存在:
对于 3 位数的数字,它不可能大于 243 = (9*9*3)
。在最坏的情况下,算法可能会在 243 以下的所有数字上循环,但它不会无限期地进行下去,所以我们排除第三种选择。
class Solution {
public:long totalSum(long n){long totalSum = 0;while(n>0){int d = n % 10;totalSum += d * d;n = n / 10;}return totalSum;}bool isHappy(int n) {std::unordered_set<long> hashset;while(!hashset.count(n) && n!= 1){hashset.insert(n);n = totalSum(n);}return n==1;}
};