模块一——双指针：202.快乐数

题目描述

题目链接：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;
    }
};