题目描述

题目链接：202.快乐数

为了方便叙述，将对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平方和这⼀个操作记为x操作；
题目告诉我们，当我们不断重复操作的时候，计算⼀定会「死循环」，死循环的方式有两种：

1. 情况⼀：⼀直在1中死循环，即1 -> 1 -> 1 -> 1…
2. 情况⼆：在历史的数据中死循环，但始终变不到1

由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在情况⼀中进行中，还是在情况二中进行，就能得到结果。

简单证明

1. 经过⼀次变化之后的最⼤值9² *10 = 810 ( 2³¹-1=2147483647 。选⼀个最大的9999999999 )，也就是变化的区间在[1, 810] 之间；
2. b. 根据「鸽巢原理」，⼀个数变化811 次之后，必然会形成⼀个循环；
3. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。

补充知识

如何求⼀个数n每个位置上的数字的平⽅和。

a.把数n 每⼀位的数提取出来：
循环迭代下⾯步骤：

• int t = n % 10 提取个位；

• n /= 10 ⼲掉个位；

直到n 的值变为0 ；
b. 提取每⼀位的时候，⽤⼀个变量tmp 记录这⼀位的平⽅与之前提取位数的平⽅和
tmp = tmp + t * t

算法原理

根据上述的题⽬分析，我们可以知道，当重复执⾏x 的时候，数据会陷⼊到⼀个「循环」之中。⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是1 ，那么这个数⼀定是快乐数；如果相遇位置不是1 的话，那么就不是快乐数。

代码实现

class Solution {
public:
    int bitSum(int n)//返回n这个数每一位上的平方和
    {
        int sum = 0;
        while(n)
        {
            int tmp = n % 10;
            sum += tmp * tmp;
            n = 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;
    }
};