快乐数原题地址

方法一：哈希集合

定义函数getNext(n)，返回n的所有位的平方和。一直执行n=getNext(n)，最终只有2种可能：

1. n停留在1。
2. 无限循环且不为1。

证明：情况1是存在的，如力扣的示例一：

接下来只需证明，反复执行getNext操作，最终一定会无限循环（停留在1可以理解为无限的1->1循环）。

分类讨论：

1. n的位数小于等于3，那么getNext(n)<=getNext(999)=243，那么反复执行getNext(n)，执行244次以上，根据抽屉原理，一定会出现循环。
2. n的位数大于3，如n为4位数，执行getNext(n)后，n的位数会减小，直到变为情况1。

所以，我们可以使用如下算法：反复执行n=getNext(n)，会出现下面3种情况：

1. n=1，说明原来的n是快乐数。
2. n不在哈希表中，则把n插入哈希表。
3. n在哈希表中，且n≠1，说明n已经进入循环，原来的n不是快乐数。

// 方法一：哈希集合
class Solution {// 计算n的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}
public:bool isHappy(int n) {unordered_set<int> hashtable;while (n != 1){// 若哈希表中没有n，就添加n，否则不是快乐数if (!hashtable.count(n)){hashtable.insert(n);}else{return false;}n = getNext(n);}return true;}
};

方法二：快慢指针（龟兔赛跑、弗洛伊德循环查找算法）

考虑到反复执行n=getNext(n)，一定会进入循环，参考判断链表是否带环的思路，定义fast和slow，slow每次执行slow=getNext(slow)一次，fast每次执行fast=getNext(fast)两次，那么slow和fast最终一定会在循环内相遇。若相遇时slow=fast=1，则n为快乐数，否则不是快乐数。

这是因为若链表带环，最终fast和slow一定会入环，且每次fast比slow多走一步，fast和slow的距离缩短一步，最终距离一定会减为0，两者相遇。

// 方法二：快慢指针法
class Solution {// 计算n的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}
public:bool isHappy(int n) {int slow = n;int fast = getNext(slow);while (slow != fast){// 慢指针一次走一步slow = getNext(slow);// 快指针一次走两步fast = getNext(getNext(fast));}return slow == 1;}
};

方法三：数学

根据方法一所述，反复执行n=getNext(n)，n一定会跌为三位数以下，且进入循环。使用硬编码穷举，最终的循环一定是...,4,16,37,58,89,145,42,20,4,...或者...1...

所以只需要提前把循环中的数存储在哈希表中，反复执行n=getNext(n)，会出现3种情况：

1. n在哈希表中，说明已经进入循环，原来的n不是快乐数。
2. n=1，说明原来的n是快乐数。
3. n不在哈希表中。

// 方法三：数学
class Solution {// 计算n的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}
public:bool isHappy(int n) {while (1){// 最终要么为1，要么进入循环if (n == 1){return true;}else if (cycleMembers.count(n)){return false;}n = getNext(n);}}
private:static unordered_set<int> cycleMembers;
};unordered_set<int> Solution::cycleMembers = { 4,16,37,58,89,145,42,20 };