https://leetcode.com/problems/happy-number/
給定一個(gè)數(shù)字找蜜，每一次拿出這個(gè)數(shù)字 abc 的每一位執(zhí)行
猿诸，得到一個(gè)新的數(shù)婚被，然后再把新的數(shù)進(jìn)行逐位平方取和，如果最后面得到的值為1梳虽，那么這個(gè)數(shù)就是 happy number
分析：
對(duì)于一個(gè)數(shù)A址芯，經(jīng)過(guò)一系列上面的操作后，達(dá)到數(shù)字B窜觉，經(jīng)過(guò)一系列操作谷炸，最后還會(huì)到數(shù)字B，即 A --> B --> B --> B禀挫，因此我們需要找到是否出現(xiàn)了循環(huán)
- 這里采用快慢指針的方法旬陡，快的比慢的每次多跑2步，這樣子快的會(huì)追上慢的语婴，形成一個(gè)環(huán)描孟；出現(xiàn)這種情況后再判斷此時(shí)的值是否是1，如果是1就是快樂(lè)數(shù)
- 也可以使用 hashset, 判斷經(jīng)過(guò)操作后的值是否之前出現(xiàn)了砰左，由于hashset需要占據(jù)空間匿醒，因此這里不采用
class Solution {
public:
bool isHappy(int n) {
int n1 = n, n2 = next(n);
while(n1!=n2 && n2 != n)
{
n1 = n2;
n2 = next(n2);
}
if(n1==1)
return true;
else
return false;
}
private:
int next(int n)
{
int result=0, temp=0;
while(n)
{
temp = n%10;
result += temp*temp;
n/=10;
}
return result;
}
};
還有一種方法：對(duì)于非快樂(lè)數(shù)，最后面肯定會(huì)到達(dá)4（待證明）菜职，因此只要判斷每次經(jīng)過(guò)上述操作是否得到4
class Solution {
public:
bool isHappy(int n) {
int result=0;
while(n!=1 && n!=4){
int result=0;
while(n)
{
result += (n%10) * (n%10);
n/=10;
}
n = result;
}
return n==1;
}
};
