題目:

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

給定一個數字,決定它是不是happy number
happy number是指對一個數重複做各位數平方相加處理,最終結果會是1的數
ex:1^2+9^2=82
8^2+2^2=68
6^2+8^2=100
1^2+0^2+0^2=1
所以19是happy number

我覺得一個數不是happy number的原因
在於它在做各位數平方相加處理時會出現循環
因此我寫了一個hash set來記錄出現過的值

class Solution:
    def isHappy(self, n: int) -> bool:
        s=set()
        while True:
            if n==1:
                return True
            i=0
            while n:
                i=i+(n%10)**2
                n=n//10
            if i in s:
                return False
            s.add(i)
            n=i

對該數不斷做各位數平方相加,同時紀錄出現過的值
一旦出現1就回傳True
一旦出現set裡的數就回傳False
後面證明我的想法是對的(本來還抱持著一定會超時的想法去丟)
最後執行時間35ms(faster than 93.04%)

討論區有人證出非happy number計算過程中一定會出現4

class Solution:
    def isHappy(self, n: int) -> bool:
        while True:
            if n==1:
                return True
            i=0
            while n:
                i=i+(n%10)**2
                n=n//10
            if i==4:
                return False
            n=i

我是沒特別去證明這件事啦
不過這樣就不用用到hash set了
速度跟記憶體使用都會好一些
最後執行時間32ms(faster than 96.67%)

那我們下題見