[LintCode/LeetCode] Perfect Squares

sydMobile 發布于2019-08-14 16:23 / 3242人閱讀

摘要：動態規劃法建立空數組從到每個數包含最少平方數情況，先所有值為將到范圍內所有平方數的值賦兩次循環更新，當它本身為平方數時，簡化動態規劃法四平方和定理法

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

Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9

Note

這道題在OJ有很多解法，公式法，遞歸法，動規法，其中公式法時間復雜度最優（four square theorem）。
不過我覺得考點還是在動規吧，也更好理解。

Solution

1. 動態規劃法

public class Solution {
    public int numSquares(int n) {
        //建立空數組dp：從0到n每個數包含最少平方數情況，先fill所有值為Integer.MAX_VALUE;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        //將0到n范圍內所有平方數的dp值賦1；
        for (int i = 0; i*i <= n; i++) {
            dp[i*i] = 1;
        }
        //兩次循環更新dp[i+j*j]，當它本身為平方數時，dp[i+j*j] < dp[i]+1
        for (int i = 0; i <= n; i++) {
            for (int j = 0; i+j*j <= n; j++) {
                dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j]);
            }
        }
        return dp[n];
    }
}

2. 簡化動態規劃法

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
            for (int j = 0; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

3. 四平方和定理法

public class Solution {
    public int numSquares (int n) {
        int m = n;
        while (m % 4 == 0)
            m = m >> 2;
        if (m % 8 == 7)
            return 4;
        int sqrtOfn = (int) Math.sqrt(n);
        if (sqrtOfn * sqrtOfn == n) //Is it a Perfect square?
            return 1;
        else {
                for (int i = 1; i <= sqrtOfn; ++i){
                    int remainder = n - i*i;
                    int sqrtOfNum = (int) Math.sqrt(remainder);
                    if (sqrtOfNum * sqrtOfNum == remainder)
                        return 2;
                }
            }
        return 3;
    }
}

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

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

[LintCode/LeetCode] Maximal Square

摘要：類似這種需要遍歷矩陣或數組來判斷，或者計算最優解最短步數，最大距離，的題目，都可以使用遞歸。 Problem Given a 2D binary matrix filled with 0s and 1s, find the largest square containing all 1s and return its area. Example For example, given t...

Drinkey 2019-08-14 15:14 評論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
[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
leetcode279. Perfect Squares

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

reclay 2019-08-15 14:20 評論0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 評論0 收藏0