AlgoPressAppearance
0202-快乐数
https://leetcode.cn/problems/happy-number
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
提示：
- 1 <= n <= 2^31 - 1
思路1 : 哈希表
可以不停的模拟运算，为了防止死循环，将当前数字加入到hash表中，当该数字出现在hash表中，说明不是快乐数
参考代码
csharp
public class Solution {
public bool IsHappy(int n) {
Dictionary<int,int> dict = new Dictionary<int,int>();
while(n != 1){
if(dict.ContainsKey(n)){
return false;
}
dict.Add(n,n);
int sum = 0;
while(n > 0){
sum += (n % 10) * (n % 10);
n = n / 10;
}
n = sum;
}
return true;
}
}
思路2 : 快慢指针法
如果不是快乐数，那么以next组成的链表，必然会成环。 使用快慢指针法，如果发现环(此时 slow = fast)，就说明不是快乐数，退出循环 最后根据结果是否为1判断是否为快乐数
csharp
public class Solution{
private int GetNext(int n){
int sum = 0;
while(n > 0){
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
public bool IsHappy(int n){
int slow = GetNext(n);
int fast = GetNext(GetNext(n));
while(slow != fast && slow != 1){
slow = GetNext(slow);
fast = GetNext(GetNext(fast));
}
return slow == 1;
}
}