利口 202. 快乐数

力扣 202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例：

解析：
这道题主要看第二个条件：重复第一个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
一个快乐数19 -> 82 -> 68 -> 100 -> 1.
对于一个非快乐数他的平方和序列会陷入一个循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。

情况1：这个数循环执行，过程1要么就变变变，变成1。
情况2：这个数不是快乐数，循环执行过程1，变变变，一直变不成1，且进入到一个循环里面，在循环里一直转圈。

我们可以把这两种情况都归类为一种情况。
情况一也是情况2的一种：19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1 -> 1…。
不过它最后执行循环的都是1。
可以把它抽象想想成如下图所示

我们把循环部分抽象想像成环，之后再只需要判断这个环里的数据是否为1即可，如果不为1，那就是非快乐数。
那么我们首先要判断该结构是否有环状结构。
可以用快慢双指针的思路来解决。
那么解法就是：

1. 定义快慢指针
2. 慢指针每次向后移动一步，快指针每次走两步。
3. 因为快乐数一定会相遇，相遇点肯定就在环形结构中，只需要判断相遇点是否唯一即可。

我们在此题上把双指针的抽象思路具体为把数看成指针：
slow = fast = 2；
slow走一步：
slow执行一次过程1。slow = 2 -> slow = 4;
fast走两步：
fast执行两次过程1。fast = 2 -> fast = 4 -> fast = 16;

补充：
没有条件2这种只有：1和无限循环这样的限制
该题还会有第三种情况：会一直往后走，永远不会重复，不会形成环结构。

但是其实第三种情况是永远不可能出现的。

代码实现：

int bitSum(int n)//返回这个数每一位上的平方和
  {
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
  }
bool isHappy(int n) {
     int slow = n, fast = bitSum(n);
   
     while(slow != fast)
     {
         slow = bitSum(slow);
         fast = bitSum( bitSum(fast));
     
     }
     //相遇之后只需判断相遇位置的值即可
     return slow == 1;

 }