• 难度：简单
• 本题涉及算法： 算数 用HashSet检测循环 快慢指针法
• 思路： 算数 用HashSet检测循环 快慢指针法
• 类似题型:

  • 876. 链表的中间结点

题目 202. 快乐数

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

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

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

示例：

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

方法一 算数

解题思路

• 根据题意 ，可得出伪代码

  def getNum(n):
    while n!=0:
        a = n%10
        n //= 10
    return a
  

• 使用 divmod 方法

  def get_next(number):
    total_sum = 0
    while number > 0:
        number, digit = divmod(number, 10)
        total_sum += digit ** 2
    return total_sum
  

• 根据题目发现判断条件
  1. 列出所有可能的条件

代码

class Solution:
    def isHappy(self, n: int) -> bool:

        cycle_members = {4, 16, 37, 58, 89, 145, 42, 20}

        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2
            return total_sum

        while n != 1 and n not in cycle_members:
            n = get_next(n)

        return n == 1

一路debug 得出的答案

• 根据题目发现判断条件
  1. 当 sumNum = 1 返回True
  2. 当 sumNum = 7 返回True 需要多 n = 1111111 单独判断
  3. 当 1 < sumNum < 10 即 循环后 n = 2 和 3 的会出现 无限循环的情况
  4. 当 sumNum > 10 ,则 赋值 n = sumNum 继续循环

代码

class Solution:
    def isHappy(self, n: int) -> bool:
        sumNum = 0;
        while n!=0:
            sumNum += (n%10)*(n%10)
            n //= 10
            if n == 0:
                if sumNum == 1 or sumNum==7:
                    return True
                if sumNum<10:
                    return False
                else :
                    n = sumNum
                    sumNum = 0

方法二 用 HashSet 检测循环

解题思路

1. 最终会得到 11。
2. 最终会进入循环。
3. 值会越来越大，最后接近无穷大。

• 检查数字是否在哈希集中需要 O(1) 的时间，而对于其他数据结构，则需要 O(n) 的时间

  代码

  ```python func isHappy(n int) bool { m := map[int]bool{} for ; n != 1 && !m[n]; n, m[n] = step(n), true { } return n == 1 }

func step(n int) int { sum := 0 for n > 0 { sum += (n%10) * (n%10) n = n/10 } return sum }

### 方法三 快慢指针法
#### 解题思路
通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。

意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。

不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。


```python

def isHappy(self, n: int) -> bool:  
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum

    slow_runner = n
    fast_runner = get_next(n)
    while fast_runner != 1 and slow_runner != fast_runner:
        slow_runner = get_next(slow_runner)
        fast_runner = get_next(get_next(fast_runner))
    return fast_runner == 1