# 202. Happy Number

{% embed url="<https://leetcode.com/problems/happy-number/>" %}

### Hashset 解法

判断n是否有某性质，先确定处理n可能会遇到的情况：

1. n不断变小，直到变成1 => n is happy
2. n会陷入循环 => n is not happy
3. n不断变大 => n is not happy

很容易看出3是不可能的，题目中这种处理过程只会n的位数落在一个区间内：

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-MAK7uhusfQJ2ARKxsBj%2F-MANO2xq-3DKqKuYVeZA%2Fimage.png?alt=media\&token=1aa46480-24df-4afd-8e92-418d5a502486)

所以处理情况2就行了，判断陷入循环，即返回 false。

```python
class Solution:
    def isHappy(self, n: int) -> bool:
        explored = set()
        
        while n not in explored:
            if n == 1: return True
            explored.add(n)
            n = sum([int(d)**2 for d in str(n)])
            
        return False
```

这边因为对n的所有digit一起采取sum操作，而且是用的python，所以讨巧简化了写法， 但`位操作` "picking digits off one-by-one" 本身是个常用操作，记忆一下常规写法比较好：

```python
n, digit = divmod(n, 10)
'''
input: n = 19
output: n = 10, digit = 9
'''
```

### Floyd's Cycle-Finding Algorithm

还有另一个经常用于判断链表中是否存在循环的算法：`Floyd's Cycle-finding`. [141. Linked List Cycle ](https://leetcode.com/problems/linked-list-cycle/)就是一个好的应用case.

简单的说就是龟兔赛跑，如果有圈儿，乌龟兔子总会再次相遇（乌龟被兔子套圈儿）。实现起来就是用快慢指针两个一起跑，遇上了就是有圈儿，快指针到终点（1）说明没圈儿。

```python
class Solution:
    def isHappy(self, n: int) -> bool:
        def SquareSum(n):
            return sum([int(d)**2 for d in str(n)])
        
        slow = n
        fast = SquareSum(n)
        while True:
            slow = SquareSum(slow)
            fast = SquareSum(SquareSum(fast))
            if slow != fast: continue
            else: break
                
        return slow == 1
```
