[Leetcode] Perfect Squares 完美平方数

Moxmi 发布于2019-08-14 12:33 / 784人阅读

摘要：动态规划复杂度时间空间思路如果一个数可以表示为一个任意数加上一个平方数，也就是，那么能组成这个数最少的平方数个数，就是能组成最少的平方数个数加上因为已经是平方数了。

Perfect Squares

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.

动态规划 复杂度

时间 O(N^2) 空间 O(N)

思路

如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。

代码

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        // 将所有非平方数的结果置最大，保证之后比较的时候不被选中
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 将所有平方数的结果置1
        for(int i = 0; i * i <= n; i++){
            dp[i * i] = 1;
        }
        // 从小到大找任意数a
        for(int a = 0; a <= n; a++){
            // 从小到大找平方数bｘb
            for(int b = 0; a + b * b <= n; b++){
                // 因为a+b*b可能本身就是平方数，所以我们要取两个中较小的
                dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);
            }
        }
        return dp[n];
    }
}

专线服务服务器托管平方数 java 平方数 java平方数判断完美数

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

转载请注明本文地址：https://www.ucloud.cn/yun/64556.html

[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
leetcode279. Perfect Squares

摘要：题目要求判断一个数字最少由几个平方数的和构成。思路一暴力递归要想知道什么样的组合最好，暴力比较所有的结果就好啦。当然，效率奇差。代码如下思路三数学统治一切这里涉及了一个叫做四平方定理的内容。有兴趣的可以去了解一下这个定理。题目要求 Given a positive integer n, find the least number of perfect square numbers (...

reclay 2019-08-15 14:20 评论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] 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 PHP题解--D34 977. Squares of a Sorted Array

摘要：题目链接题目分析本题比较简单。对给定数组的每一个数字的平方。并对结果进行排序。思路遍历每一个元素，相乘自身。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 977. Squares of a Sorted Array 题目链接 977. Squares of a Sorted Array 题目分析本题比较简单。对给定数组的每一个数字的平方。并对结果进行排序。思路遍历每一个元素，...

Kaede 2019-07-01 12:41 评论0 收藏0