木门行业做网站有什么好处,2021给个手机能看的地址,WordPress模板购买过程,莱芜雪野湖国际会议中心LeetCode 202. 快乐数
1、题目
力扣题目链接#xff1a;202. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为#xff1a;
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1#xff0c;…LeetCode 202. 快乐数
1、题目
力扣题目链接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
2、哈希法
代码
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) { // 创建一个无序集合set用于存储平方和以便检查是否有重复 unordered_setint set; int sum 0; // 无限循环直到sum等于1或set中已有sum时停止 while (1) { // 计算n的平方和 sum getSum(n); // 如果平方和sum等于1说明是快乐数返回true if (sum 1) { return true; } // 如果set中已有sum说明不是快乐数返回false if (set.find(sum) ! set.end()) { return false; } else { // 将新的平方和sum加入set中并对n进行更新为下一次循环做准备 set.insert(sum); n sum; } } }
};复杂度分析 时间复杂度: O(logn) 空间复杂度: O(logn)
3、双指针法
代码
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) { // 计算n的平方和赋值给slowslow可以看作是n的移动轨迹或者说是“速度慢的点” int slow getSum(n); // 计算slow的平方和赋值给fastfast可以看作是“速度快的点”或者说是指向slow的“指针” int fast getSum(getSum(n)); // 当fast不等于1且slow不等于fast时执行下面的循环 while (fast ! 1 slow ! fast) { // slow的值加1即求slow的平方和相当于让slow这个“点”移动到新的位置 slow getSum(slow); // fast的值加1即求fast的平方和相当于让fast这个“指针”指向新的位置 fast getSum(getSum(fast)); } // 返回fast是否等于1的结果即判断是否循环到最后得到1如果是则返回true真否则返回false假 return fast 1; }
};复杂度分析 时间复杂度O(logn) 空间复杂度O(1)
