【算法专题突破】双指针 - 快乐数（3）

1. 题目解析

题目链接：202. 快乐数 - 力扣（Leetcode）

这道题的题目也很容易理解，

看一下题目给的示例就能很容易明白，

但是要注意一个点，最后有可能无限循环无法到达1。

这个时候我们就要想一下怎么判断他是无线循环呢？

实际上，当他在进行平方和的计算中，同一个数字再次出现的时候，

就证明他进入无限循环了，来看个例子：

如果我们计算 2 是不是快乐数，当再次出现 4 这个数的时候，

我们就可以知道，他进入无限循环了。

2. 算法原理

我们可以想象一下，

题目给出的两种情况，其实都是一个循环，

如果是快乐数，就会一直循环得到1，

如果不是快乐数，就会按照自己的节奏循环，永远到不了1，

这个时候吗，我们就可以用快慢指针的思想来做这道题，

让一个指针走两步，一个指针走一步，当两个指针相遇的时候，

他们肯定已经开始循环了，如果相遇的时候，

值为1就是快乐数，如果值不为1就证明不是快乐数。

3. 代码编写

class Solution {
public:
    bool isHappy(int n) {
        int fast = n, slow = n;
        while(true) {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
            if(fast == slow) break;
        }
        return fast == 1;
    }
private:
    int Sum(int n) {
        int sum = 0;
        while(n) {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~