[双指针] 3. 力扣--快乐数

一. 题目描述

class Solution { public: bool isHappy(int n) { } };

二. 解题思路

下面我们称 将一个正整数替换为他每个位置上的数字的平方和的操作 为F操作。

1）题干中快乐数定义的第二点已经明确告诉我们，一个数持续进行F操作只有两种情况：
1. 重复这个数直到这个数变为1（之后，也可以看作是一个环）。
2. 无限循环但是永远到不了1（也是有环的，只不过不是在1中一直循环）。

为什么一定会成环，就不可能一条直线的无限循环下去么？

2）我们这个系列的双指针算法只是一种思想，用来标记一个位置。这个指针可以是一个真正的指针，也可以是数组下标，甚至直接是结构中存储的数据。比如本题就是直接用数做快慢指针。

3）因为有环，所以我们找到的相遇点的值一定是环内的值。相遇点的值如果是1，那么这个数就是快乐数，return true; 否则不是快乐数，return false;

4）步骤：
1. 定义快慢指针。
2. 慢指针一次走一步，快指针一次走两步。
3. 判断相遇点的值。

三. 代码实现

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