（算法）双指针——快乐数 ＜数据分块＞

1. 题⽬链接：快乐数

2. 题⽬描述：

3. 题⽬分析: 

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

        ▪ 情况⼀：⼀直在1 中死循环，即1 -> 1 -> 1 -> 1......  

        ▪ 情况⼆：在历史的数据中死循环，但始终变不到1  

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

简单证明：  

a. 经过⼀次变化之后的最⼤值9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最 ⼤9999999999 )，也就是变化的区间在[1, 810] 之间； 

b. 根据「鸽巢原理」，⼀个数变化811 次之后，必然会形成⼀个循环；

c. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。

4. 解法（快慢指针）：  

算法思路：  

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

补充知识：如何求⼀个数n每个位置上的数字的平⽅和. 

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

        i. int t = n % 10 提取个位； 

        ii. n /= 10 ⼲掉个位； 直到n 的值变为0 ； 

b. 提取每⼀位的时候，⽤⼀个变量tmp 记录这⼀位的平⽅与之前提取位数的平⽅和 

        ▪ tmp = tmp + t * t

C++算法代码： 

class Solution {
public:
     //求各位的平方和
    int Getsum(int x)
    {
        int count=0;
        while(x)
        {
            int t=x%10;
            count+=t*t;
            x/=10;
        }
            return count;
    }
    bool isHappy(int n) 
    {
        //快慢双指针，慢指针一次走一步，快指针一次走两步
        //根据数学推导，快慢指针必定会相遇
        //可能性1：进入1的循环
        //可能性2：进入不等于1的循环
        int low=n,fast=Getsum(n);
        while(low!=fast)
        {
            low=Getsum(low);    //慢指针一次走一步
            fast=Getsum(fast);  //快指针一次走两步
            fast=Getsum(fast);
        }
        //相遇后判断是哪一种循环
        if(low==1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

 Java算法代码：

class Solution
{
	public int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和 
	{
		int sum = 0;
		while (n != 0)
		{
			int t = n % 10;
			sum += t * t;
			n /= 10;
		}
		return sum;
	}
	public boolean isHappy(int n)
	{
		int slow = n, fast = bitSum(n);
		while (slow != fast)
		{
			slow = bitSum(slow);
			fast = bitSum(bitSum(fast));
		}
		return slow == 1;
	}
}