LeetCode0202. 快乐数

一. 题目

1. 题目
   

2. 示例
   

二. 方法一: 集合Set

1. 解题思路

   1. 求出n的每一位数字的平方和
   2. 判断结果是否为1
   3. 如果结果为1, 则直接返回True
   4. 如果结果不为1, 则开始循环遍历
   5. 将计算出的结果存放在集合中
   6. 如果结果在集合中已经存在了, 则说明陷入了循环. 则返回false

2. 解题代码

   def isHappy(self, n: int) -> bool:
       arr = set()
       while n != 1:
           res = 0
           while n > 0:
               res += (n % 10) * (n % 10)
               n = n // 10
           if res not in arr:
               arr.add(res)
           else:
               return False
           n = res
       return True
   

3. 分析
   时间复杂度: O(logn)
   空间复杂度: O(logn)
   官方证明:
   

三. 方法二: 快慢指针

1. 解题思路
   方法1存在的问题: 由于每次都需要将结果n存放到集合中, 最终可能会导致集合过大.出现空间不够的情况

   1. 创建两个指针(快指针和慢指针), 其中快指针一次移动两步, 慢指针一次移动一步.
   2. 如果快指针指向的元素不为1, 且快指针和慢指针所指的元素不相等, 则继续遍历
   3. 如果快指针等于慢指针, 则退出循环
   4. 此时判断快指针指向的元素是否为1
   5. 如果为1, 则是快乐数, 如果不为1, 则陷入了死循环, 返回False

2. 解题代码

   def getNext(self, n: int):
       res = 0
       while n > 0:
           res += (n % 10) ** 2
           n = n // 10
       return res
   
   
   def isHappy(self, n: int) -> bool:
       slow_runner = n
       fast_runner = self.getNext(n)
       while fast_runner != 1 and slow_runner != fast_runner:
           slow_runner = self.getNext(slow_runner)
           fast_runner = self.getNext(fast_runner)
           fast_runner = self.getNext(fast_runner)
   
       return fast_runner == 1
   

3. 分析
   时间复杂度: O(logn)
   空间复杂度: O(1)