202. Happy Number

發表於 分類於 ， 閱讀次數： 文章字數： 1.2k

種類 : hash table
難度 : easy
題目 : 202. Happy Number

思維邏輯

  1. 迴圈
    1. int轉str逐一分割，再str轉int計算結果
    2. 檢核結果是否為1，返回True
    3. 檢核是否在set中，返回False
    4. 將結果加入set

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isHappy(self, n: int) -> bool:
        # init
        s = set()
        num = 0

        while True:
            # calculate
            for i in str(n):
                num += (int(i)**2)

            # check num = 1
            if num == 1: return True
            
            if num in s:
                return False
            s.add(num)
            n = num
            num = 0

n的位數: d
時間複雜度: O(d) -> O(log n) -> O(1)
空間複雜度: O(1)

難點

  1. 迴圈何時結束: 當計算出的結果重複時
  2. 題目一開始沒讀懂，以為是計算結果為 0與1的組合

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
集合
將計算拆成function
"""
class Solution:
    def isHappy(self, n: int) -> bool:        
        record = set()

        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
            if n in record:
                return False
            else:
                record.add(n)

    def get_sum(self,n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10) # 返回n/10的 商 & 餘數
            new_num += r ** 2
        return new_num

時間複雜度: O(logn)
空間複雜度: O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
快慢指針
"""
class Solution:
   def isHappy(self, n: int) -> bool:        
       slow = n
       fast = n
       while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)):
           slow = self.get_sum(slow)
           fast = self.get_sum(self.get_sum(fast))
           if slow == fast:
               return False
       return True
   def get_sum(self,n: int) -> int: 
       new_num = 0
       while n:
           n, r = divmod(n, 10)
           new_num += r ** 2
       return new_num

時間複雜度: O(logn)
空間複雜度: O(logn)