leetcode279. Perfect Squares

reclay 发布于2019-08-15 14:20 / 1574人阅读

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

题目要求

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

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

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