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

题目描述

202. 快乐数

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

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

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

示例：

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

解题思路

Leetcode官方题解: 快乐数

按照规则, 数字一个一个推演, 可能会发生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作为链表结束的标志(没有环). 使用快慢指针, 如果存在环, 在某一步肯定会遇到快慢指针对应的数值相等的情况.

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