LeetCode #202 Happy Number 快樂號碼

Klook.com
文章觀看次數: 281

LeetCode題目翻譯

英文原文如下

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.

中文翻譯

寫一個演算法用來確認數字 n 是否快樂

確認一個快樂號碼需按照以下幾個步驟

  • 從任意正整數開始，將它以每位數的平方的總和取代
  • 重複這個步驟，直到它等於 1 或是陷入無窮迴圈 ( 不包含1 )
  • 那些結果等於 1 的號碼就是快樂的

n 為快樂號碼即回傳 true，反之則回傳 false

範例及題目限制

範例及題目限制

範例1 下面寫得相當詳細，想不到範例2就直接 false

實在太偷懶了，讓我們來補一下過程( 如果沒太長的話 …

2² = 4
4² = 16
1² + 6² = 37
3² + 7² = 58
5² + 8² = 89
8² + 9² = 145
1² + 4² + 5² = 42
4² + 2² = 20
2² + 0² = 4  >> 陷入無窮迴圈

解題思路

從上面兩個範例可以看出，判斷陷入無窮迴圈是這次的課題

而最簡單的方法就是把有跑過的數字記錄下來，有跑到就是陷入迴圈了

C# 解決方案

方案1

public class Solution {
    public bool IsHappy(int n) {
        
        List<int>used = new List<int>();

        while(n>0)
        {
            int tmp = 0;
            while(n>0)
            {
                int i = n%10;

                tmp += i*i;
                n = n/10;
            }

            if(used.Contains(tmp))
            {
                return false;
            }
            else
            {
                used.Add(tmp);    
            }
            

            if(tmp==1)
            {
                return true;
            }

            n = tmp;

        }
        
        return false;
    }
}

Java解決方案

方案1

class Solution {
    public boolean isHappy(int n) {
        List<Integer>used = new ArrayList<Integer>();

        while(n>0)
        {
            int tmp = 0;
            while(n>0)
            {
                int i = n%10;

                tmp += i*i;
                n = n/10;
            }

            if(used.contains(tmp))
            {
                return false;
            }
            else
            {
                used.add(tmp);    
            }
            

            if(tmp==1)
            {
                return true;
            }

            n = tmp;

        }
        
        return false; 
    }
}

運行時間 : 1ms、1ms、1ms

Python3解決方案

方案1

class Solution:
    def isHappy(self, n: int) -> bool:
        used = []

        while(n>0):
            tmp = 0
            while(n>0):
                i = n%10

                tmp += i*i
                n = n//10

            if(tmp in used):
                return False
            else:
                used.append(tmp)

            if(tmp==1):
                return True
            
            n = tmp

        return False

*Python 的 雙斜線 ( // ) 才能取到整數

JavaScript解決方案

方案1

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    let used = new Set();

    while(n>0)
    {
        let tmp = 0;
        while(n>0)
        {
            let i = n%10;

            tmp += i*i;
            n = Math.floor(n/10);
        }

        if(used.has(tmp))
        {
            return false;
        }
        else
        {
            used.add(tmp);    
        }
        

        if(tmp==1)
        {
            return true;
        }

        n = tmp;

    }
    
    return false; 
};

結論

惠子曾與莊子有過一段有名的談話 「子非魚，安知魚之樂？」

在這一題中，我也想問 「子非數，安知數之樂？」

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我分享或是收藏，我都會很感激的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Happy Number – LeetCode

延伸閱讀 : 看莊子與惠子討論魚 「知魚之樂」辯論︰莊子跟惠子說甚麼？ – The News Lens 關鍵評論網

隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *