iT邦幫忙

0

簡介四平方和定理- leetcode 279. Perfect Squares

這邊簡介一題蠻數學的leetcode問題,
題目說給定一個正整數n,
回傳最少需要幾個平方數的總和等於n。

參考題目:279. Perfect Squares

例如12=4+4+4,最少三個平方數,
13=4+9,最少兩個平方數,
7 = 1+1+1+4,最少四個平方數

數論上有一個著名的的四平方和定理
說每個正整數均可表示為4個整數的平方和

因此這一題就很單純了,
直接暴力搜索看看這個數字可不可以表示成1, 2, 或3個數字的平方和,
如果不行的話直接回傳4,
就不會超時了

python程式碼

class Solution:
    def numSquares(self, n: int) -> int:
        if abs(round(pow(n,0.5))-pow(n,0.5))<=1e-6:
            return 1
        for i in range(int(n**0.5)+1):
            num = n-i*i
            if num>0 and abs(round(pow(num,0.5))-pow(num,0.5))<=1e-6:
                return 2
        for i in range(int(n**0.5)+1):
            for j in range(i,int(n**0.5)+1):
                num = n-i*i-j*j
                if num>0 and abs(round(pow(num,0.5))-pow(num,0.5))<=1e-6:
                    return 3
        return 4

其中,用來檢驗一個數字是否為平方數的方法,
我用abs(round(pow(n,0.5))-pow(n,0.5))<=1e-6來判斷,
如果一個數字開根號在四捨五入到整數位,
與該數字開根號夠接近0,
就相信它是平方數


尚未有邦友留言

立即登入留言