[LintCode/LeetCode] Perfect Squares

sydMobile 发布于2019-08-14 16:23 / 3208人阅读

摘要：动态规划法建立空数组从到每个数包含最少平方数情况，先所有值为将到范围内所有平方数的值赋两次循环更新，当它本身为平方数时，简化动态规划法四平方和定理法

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;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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