279、完全平方数

leetcode

Created At : 2020-07-26 00:19

Count:786 Views 👀 :

Comment:

示例 1:
示例 2:

思路

代码

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思路

本身就是完全平方数也得找几个数字求和
最少是两个
对1～n之内的所有的完全平方数进行遍历
求dp[i]，min(lenth) of a[] to add to equal to i

dp[0] = 0;
dp[1] = 1;
dp[2] = dp[1]+dp[1] = 2;
dp[3] = dp[2]+dp[1] = 2;
dp[4] = 1;
dp[5] = dp[4]+dp[1] = 2;
dp[6] = dp[4]+dp[2] = 3;
dp[7] = dp[4]+dp[3] = 3;
dp[8] = dp[4]+dp[4] = 2;
dp[26] = dp[25] + dp[1] = 2;

数学定理
- 四平方定理：
  - 任何一个正整数都可以表示成不超过四个整数的平方之和。
  - 推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)

代码

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1;i*i < n;i++) {
            dp[i*i] = 1;
        }
        if(dp[n] == 1) return dp[n];
        for (int i = 2;i <= n;i++) {
            // 不对
            for (int j = i-1;j >= 1;j--) {
                // 寻找最近的一个完全平方数字
                if (dp[j] == 1) {
                    // i-j <= j 一定成立
                    dp[i] = dp[j] + dp[i-j];
                    break;
                }
            }
        }
        return dp[n];
    }
}

动态规划
- 扫描全部的已知解求最小值

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 1;i*i < n;i++) {
            dp[i*i] = 1;
        }
        if(dp[n] == 1) return dp[n];
        for (int i = 2;i <= n;i++) {
            if (dp[i] != 1) {
                dp[i] = i;
                for (int j = i - 1;j >= 0;j--) {
                    if (dp[j] == 1) {// 有效值
                        // 更新最少的完全平方数的个数
                        dp[i] = Math.min(dp[i],dp[i-j]+1);
                    }
                }
            }
        }
        return dp[n];
    }
}

// 参考
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程

            }
        }
        return dp[n];
    }
}

// 作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/perfect-squares/solution/hua-jie-suan-fa-279-wan-quan-ping-fang-shu-by-guan/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四平方定理：任何一个正整数都可以表示成不超过四个整数的平方之和。
- 推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)

class Solution {
    public int numSquares(int n) {
        // 求8*b + 7
        while (n % 4 == 0) {
            n = n / 4;
        }
        // 判断 是否满足
        if (n % 8 == 7) {
            return 4;
        }

        for (int i = 0; i * i <= n; ++i) {
            int j = (int) Math.sqrt(n - i * i);
            if (j * j + i * i == n) {
                if (i == 0) {// 本身就是管理
                    return 1;
                }
                return 2;// i & j
            }
        }
        return 3;// 排除法，剩下的就是 3个
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com