用hash记录是否出现了循环
对于 33 位数的数字，它不可能大于 243243。这意味着它要么被困在 243243 以下的循环内，要么跌到 11。44 位或 44 位以上的数字在每一步都会丢失一位，直到降到 33 位为止。所以我们知道，最坏的情况下，算法可能会在 243243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 11。但它不会无限期地进行下去，所以我们排除第三种选择。
作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isHappy(int n) {
unordered_set<int> set;
while(set.count(n) == 0)
{
set.insert(n);
int tmp = 0;
while(n)
{
int num = n % 10;
n /= 10;
tmp += num * num;
}
if(tmp == 1)
return true;
n = tmp;
}
return false;
}
};
|
快慢指针找环路
虽然没有显式的链表，但是每个数字都是一个节点，如果有环路他们终究会相交，如果没有，快指针就会走向1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool isHappy(int n) {
int walker = n;
int runner = n;
while(runner != 1)
{
walker = getNext(walker);
runner = getNext(getNext(runner));
if(runner == walker)
break;;
}
return runner == 1;
}
private:
int getNext(int n)
{
int tmp = 0;
while(n)
{
int num = n % 10;
tmp += num * num;
n /= 10;
}
return tmp;
}
};
|