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

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 快乐数（3）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

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

【算法专题突破】双指针 - 快乐数（3）,算法专题训练,c++,算法

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

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

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

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

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

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

【算法专题突破】双指针 - 快乐数（3）,算法专题训练,c++,算法

如果我们计算 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;
    }
};