力扣双指针算法题目：快乐数

目录

1.题目

2.思路解析

3.代码展示

1.题目

. - 力扣（LeetCode）

2.思路解析

题目意思是将一个正整数上面的每一位拿出来，然后分别求平方，最后将这些数字的平方求和得到一个数字，如此循环，如果在此循环中得到了这个和为’1‘，那么就return true；反之false

我们任意取几个数字距离，发现可以得到如下规律

由图可知，这是一个有环链表，说起链表问题，在判断一个链表是否有环的时候，我们常用的思想就是快慢指针思想，通常来讲就是有两个指针slow和fast，slow初始化在第一个位置，fast初始化在第二个位置，slow一次走一格，fast一次走两格，如果slow指针可以和fast指针相遇，那么就说明这个链表是有环的。

我但是这一题并不是真正的链表，所以更准确的来讲我们使用“快慢指针的思想”去解决。

也就是说我们是要想办法模拟出快慢指针的行为模式。

如上图的数字是一个循环，所以我们首先需要去考虑的是如何去将这个类似于链表的“环”构造出来

如果我输入一个数字“2”，我应该如何得到“4”呢？，那么我首先需要的是一个将输入数字“2”的每个位子上的数字拆出来然后求和的函数，于是我们先写了下面的这样一个函数

之后我们需要考虑的是如何让这个循环动起来，自动构造一个环，然后让慢指针slow每次走一个格子，快指针fast每次走两个格子达成如图所示的效果

由于纯数字结构不可能去形成环，所以我们只能用“指针”去代表这环上面的每个元素，如图，slow初始化是slow=n，n是2，fast初始化就是对n使用了一下函数bitsum

如何让慢指针slow每次推进一格，我们只要调用一次函数bitsum既可以了

如何让快指针dfast每次推进两个格子，我们只要将fast目前所代表的数字调用一下bitsum得到它后面的一个数字，再让它后面的一格数字再次调用一下bitsum就可以了，这便是如下的代码。

3.代码展示

class Solution 
{
public:
    int bitsum(int n)
    {
        int sum=0;
        while(n!=0)
        {
            int a=n%10;
            sum=sum+a*a;
            n/=10;
        }
        return sum;
    }      
    bool isHappy(int n) 
    {
        int slow=n;
        int fast=bitsum(n);
        while(fast!=slow)
        {
            slow=bitsum(slow);
            fast=bitsum(bitsum(fast));
        }
        return slow==1;
    }
};