leetcode279. Perfect Squares

reclay 發布于2019-08-15 14:20 / 1600人閱讀

摘要：題目要求判斷一個數字最少由幾個平方數的和構成。思路一暴力遞歸要想知道什么樣的組合最好，暴力比較所有的結果就好啦。當然，效率奇差。代碼如下思路三數學統治一切這里涉及了一個叫做四平方定理的內容。有興趣的可以去了解一下這個定理。

題目要求

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

判斷一個數字最少由幾個平方數的和構成。比如12=9+1+1+1=4+4+4，那么最少的數量為3。

思路一：暴力遞歸

要想知道什么樣的組合最好，暴力比較所有的結果就好啦。當然，效率奇差。

    public int numSquares(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int sqrt = (int) Math.floor(Math.sqrt(n));
        int count = Integer.MAX_VALUE;
        while(sqrt>0){
            int tmpCount = 0;
            int copy = n;
            do{
                copy -= sqrt * sqrt;
                tmpCount++;
            }while(copy > sqrt * sqrt);
            count = Math.min(count, tmpCount+numSquares(copy));
            sqrt--;
        }
        return count;
    }

思路二：動態規劃

我們可以用另一種思路來拆解n：
比如：
numSquares(1) = 1;
numSquares(2) = numSquares(1)+1
numSquares(3) = numSquares(3-1*1) + 1
numSquares(4) = 1
numSquares(5) = min(numSquares(5-1*1)+1, numSquares(5-2*2)+1)
numSquares(10) = min(numSquares(10-1*1)+1, numSquares(10-2*2)+1, numSquares(10-3*3)+1)

這樣我們就可以省去許多重復的計算。
代碼如下：

    public int numSquares_dp(int n){
        if(n<=1) return n;
        int[] min = new int[n+1];
        min[1] = 1;
        for(int i = 2 ; i<=n ; i++){
            int sqrt = (int)Math.floor(Math.sqrt(i));
            int tempMin = Integer.MAX_VALUE;
            while(sqrt-->0){
                tempMin = Math.min(tempMin, min[n-sqrt*sqrt]);
                sqrt--;
            }
            min[i] = tempMin;
        }
        return min[n];
    }

思路三：數學統治一切

這里涉及了一個叫做四平方定理的內容。有興趣的可以去了解一下這個定理。總之就是給了一個一般規律，這里貼上代碼：

    public int numSquares_math(int n){
        if(isSquare(n)) return 1;
         while ((n & 3) == 0) // n%4 == 0  
            {
                n >>= 2;  
            }
            if ((n & 7) == 7) // n%8 == 7
            {
                return 4;
            }
            
            // Check whether 2 is the result.
            int sqrt_n = (int)(Math.sqrt(n)); 
            for(int i = 1; i <= sqrt_n; i++)
            {  
                if (isSquare(n - i*i)) 
                {
                    return 2;  
                }
            }  
            
            return 3; 
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Squares perfect Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68549.html

[LeetCode] 279. Perfect Squares

Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Exampl...

mist14 2019-08-16 13:57 評論0 收藏0
LeetCode 279: Perfect Squares

摘要：題目給一個正整數問他最少能被幾個完全平方數和表示。舉例，返回，返回解法我能看懂的就只有的方法，原理如下代碼題目：給一個正整數n,問他最少能被幾個完全平方數和表示。舉例： 13=4+9，返回2；12 = 4+4+4，返回3；解法：我能看懂的就只有dynamic-programming的方法，原理如下： dp[0] = 0 dp[1] = dp[0]+1 = 1 dp[2...

codecook 2019-08-14 15:53 評論0 收藏0
[Leetcode] Perfect Squares 完美平方數

摘要：動態規劃復雜度時間空間思路如果一個數可以表示為一個任意數加上一個平方數，也就是，那么能組成這個數最少的平方數個數，就是能組成最少的平方數個數加上因為已經是平方數了。 Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4...

Moxmi 2019-08-14 12:33 評論0 收藏0
[LintCode/LeetCode] Perfect Squares

摘要：動態規劃法建立空數組從到每個數包含最少平方數情況，先所有值為將到范圍內所有平方數的值賦兩次循環更新，當它本身為平方數時，簡化動態規劃法四平方和定理法 Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) whi...

sydMobile 2019-08-14 16:23 評論0 收藏0