# \[202]\[简单]\[双指针] 快乐数

## 题目描述

[202. 快乐数](https://leetcode-cn.com/problems/happy-number/)

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

```
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
```

## 解题思路

[Leetcode官方题解: 快乐数](https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/)

按照规则, 数字一个一个推演, 可能会发生3中情况:

* 最终会得到1
* 最终会进入循环
* 值会越来越大，最后接近无穷大

| Digits | Largest       | Next |
| ------ | ------------- | ---- |
| 1      | 9             | 81   |
| 2      | 99            | 162  |
| 3      | 999           | 243  |
| 4      | 9999          | 324  |
| 13     | 9999999999999 | 1053 |

但根据上表, 可以发现, 三位数的数字, 得到的下一个值不可能大于243, 而更高位的数字只会落入到243之内, 退化为三位数. 因此不可能出现第三种情况. 而且如果不能收敛, 一定在243的范围之内循环, 最坏的情况下就是在收敛到三位数之后, 前243轮都是不同的数, 但之后的数肯定还是在243范围内, 从而形成循环.

这样我们只用考虑前两种情况. 这样就可以类比链表里寻找是否有环的题目了. 以1作为链表结束的标志(没有环). 使用快慢指针, 如果存在环, 在某一步肯定会遇到快慢指针对应的数值相等的情况.

```python
class Solution:
    @staticmethod
    def next_number(num):
        next_num = 0
        while num > 0:
            next_num += (num % 10) ** 2
            num //= 10
        return next_num

    def isHappy(self, n: int) -> bool:
        slow = fast = n
        while fast != 1:
            slow = self.next_number(slow)
            fast = self.next_number(self.next_number(fast))
            if slow == fast and slow != 1:
                return False
        return True
```