202. 快乐数(Easy)

题目描述

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

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

样例

Input：19
Output：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

题解

和上题的 142. 环形链表 II(Medium) 一样的思路，就是 龟兔算法 的另一个场景，目的是 Cycle Detect。

Python示例

class Solution:
    def isHappy(self, n: int) -> bool:
        def f(x):
            s = 0
            while x:
                s += (x % 10) ** 2
                x = x // 10
            return s

        slow = f(n)
        fast = f(f(n))
        while fast != 1 and fast != slow:
            fast = f(f(fast))
            slow = f(slow)
        return fast == 1

Go 示例

func f(x int) int {
    s := 0 
    for x != 0 {
        s = s + (x % 10) * (x % 10)
        x = x / 10
    }
    return s 
}

func isHappy(n int) bool {
    slow := f(n)
    fast := f(f(n))
    for fast != 1 && slow != fast {
        slow = f(slow)
        fast = f(f(fast))
    }
    return fast == 1
}