优先算法 —— 双指针系列 - 快乐数

1. 快乐数

题目链接：

1. 快乐数 - 力扣（LeetCode）https://leetcode.cn/problems/happy-number/description/

2. 题目解析

示例1：

示例2：

3. 算法原理

两种情况：我们可以把两种情况都看作为循环，一种循环里都为1，一种都不为1

---

但是我们还可以将两种情况和为一种情况：从本题题目可以看出本题一定会是循环，所以我们可以只需要判断环里的那个数是否为1就可以了

---

如何判断链表是否有环

1. 定义快慢指针

---

**2. 让这两个指针在环的开头开始移动，移动的时候让慢指针每次向右移动1不，快指针向右移动2步 **

---

3. 判断相遇时候位置的值，如果为1就是快乐数，否则就不是

4. 代码

class Solution {
public:
    //返回n每一位的平方和
    int Sum(int n)
    {
        int sum=0;
        while(n)
        {
            int tmp=n%10;//取n的最低位
            sum+=tmp*tmp;//将最低位的平方给sum
            n/=10;//干掉最低位
        }
        return sum;
    }

    bool isHappy(int n) {
        //cur指向第一个位置，dest指向第二个位置
        int cur=n,dest=Sum(n);
        while(cur!=dest)
        {
            cur=Sum(cur);//走一步
            dest=Sum(Sum(dest));//走两步
        }
        return cur==1;
    }
};

未完待续~