音乐网站制作教程,梦幻西游官方网站,大型网站建设建站模板,dw做的网站怎样才有域名代码随想录二刷 #xff5c; 哈希表 #xff5c; 快乐数 题目描述解题思路 代码实现 题目描述
202.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。 … 代码随想录二刷 哈希表 快乐数 题目描述解题思路 代码实现 题目描述
202.快乐数
编写一个算法来判断一个数 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
解题思路 代码实现
题目中说了会无限循环那么也就是说求和的过程中sum会重复出现当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法了。
所以这道题目使用哈希法来判断这个sum是否重复出现如果重复了就是return false 否则一直找到sum 1为止。
判断sum是否重复出现就可以使用unordered_set。
class Solution {
public:// 取各个位上的单数之和int getSum(int n) {int sum 0;while (n) {sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {unordered_setint set;// 让循环一直进行直到找出结果while (1) {int sum getSum(n);// 符合条件返回trueif (sum 1) return true;// 如果sum曾经出现过说明已经陷入无限循环return falseif (set.find(sum) ! set.end()) return false;else set.insert(sum);n sum;}}
};时间复杂度O(logn) 空间复杂度O(logn)
