【C++算法】4.双指针_快乐数

---

题目链接：

202.快乐数

---

题目描述：

---

解法

根据题目来看，可能是无限循环，也可能是快乐数。因为就相当于下图：

无限循环可以看成一个圈，快乐数得到的1也可以看成一个圈。因为对1求快乐数得到的也是1，相当于在1里循环。所以就相当于下图。

快慢双指针

1. 定义快慢指针（用数来充当指针）

   例如：n = 19

   slow = 1²+9²=82

   fast = 8²+2²=68

2. 慢指针每次向后移动一步

   快指针每次向后移动两步

3. 因为快慢指针速度不一样，所以如果存在环的话，两个指针一定会在环里的某处相遇的（前面数据结构博客里面环形链表讲过这个）博客链接🔗

---

C++ 算法代码：

class Solution 
{
public:int bitSum(int n) // 返回 n 这个数每一位上的平方和{int sum = 0;while(n)//把最后一位拿出来，然后除以10，循环直到为0为止。{int t = n % 10;sum += t * t;n /= 10;}return sum;//sum就是最终结果}bool isHappy(int n){//用数来充当指针int slow = n, fast = bitSum(n);//这里fast是n求过一次平方和的值，目的是能够顺利进入下面的循环。因为如果fast和slow都是n的话，就无法循环了while(slow != fast)//slow!=fast就一直循环{slow = bitSum(slow);//慢指针走1步fast = bitSum(bitSum(fast));//快指针走2步}return slow == 1;//slow=1就是快乐数，不是1就不是快乐数}
};

---

图解：

输入19

1. slow=19，fast=82
2. slow=82，fast=100
3. slow=68，fast=1
4. slow=100，fast=1
5. slow==fast
6. return slow==1