202. Happy Number

Loading...LeetCode

Hashset 解法

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

1. n不断变小，直到变成1 => n is happy

2. n会陷入循环 => n is not happy

3. n不断变大 => n is not happy

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

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

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" 本身是个常用操作，记忆一下常规写法比较好：

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 就是一个好的应用case.

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

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