Leetcode:279. 完全平方数

题目描述

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

示例 1:

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

示例 2:

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

思路

思路1 DP+可开方数保存

保存可开方数，然后使用$dp[i] = min(dp[i - sqrtNum[j]] + 1)　j \in 开方列表大小$

思路2 贪心法

使用一个canSqure函数依次计算是否可以由count个可开方数字加和得到，在这个过程依旧要保存可开方数，用于计算递归计算count - 1个组合而成

思路3 贪心+BFS

贪心+BFS基本思路是思路2的n元树BFS

思路4 数学公式

每个自然数都可以表示为四个整数平方和，且$n!= 4^k(8m + 7) <==> n = a^2 + b^2 + c^2$,所以只需要判断能否表示为三个可开方数之和，如果不能则为4，然后判断是否可以由两个开方数组合而成以及一个可开方数

代码

代码1

class Solution {
    public int numSquares(int n) {
        if (n == 0 || n == 1){
            return 1;
        }
        int[] dps = new int[n + 1];
        ArrayList sqrtNums = new ArrayList<>();
        for(int i = 0; i < n + 1; i++){
            if (i >= 1 && i * i <= n){
                sqrtNums.add(i * i);
            }
            dps[i] = i;
        }
        int sqrtSize = sqrtNums.size();
        for(int i = 2; i <= n; i++){
            int tempNum = 1;
            for(int j = 0; j < sqrtSize && i - sqrtNums.get(j) >= 0; j++){
                dps[i] = Math.min(dps[i], dps[i - sqrtNums.get(j)] + 1);
            }
        }
        return dps[n];
    }
}

代码2

class Solution {
    private Set squareSet;
    
    public int numSquares(int n) {
        if (n == 0 || n == 1){
            return 1;
        }
        squareSet = new HashSet<>();
        for(int i = 0; i * i <= n; i++){
            squareSet.add(i * i);
        }
        
        for(int i = 1; i <= n; i++){
            if (canSquare(n, i)){
                return i;
            }
        }
        return n;
    }
    
    private boolean canSquare(int n, int count){
        if (n < 0){
            return false;
        }
        if (count == 1){
            return squareSet.contains(n);
        }
        for(int num: squareSet){
            if (canSquare(n - num, count - 1)){
                return true;
            }
        }
        return false;
    }
}

代码4

class Solution {
    public int numSquares(int n) {
        while (n % 4 == 0){
            n /= 4;
        }
        if (n % 8 == 7){
            return 4;
        }
        if (isSquare(n)){
            return 1;
        }
        for(int i = 1; i * i <= n; i++){
            if (isSquare(n - i * i)){
                return 2;
            }
        }
        return 3;
    }
    
    private boolean isSquare(int n){
        int getSqrt = (int)Math.sqrt(n);
        return getSqrt * getSqrt == n;
    }
}