原题

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

示例 1:

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

示例 2:

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

解法

思想

以12为例。

这道题确实对时间要求比较严格，如果不过滤掉重复计算的部分会无法通过。

从目标数出发自顶向下：

由已知的目标数出发，减去比它小的平方数，这样一层一层减下去，直到获得0的那一层的层数就是答案。

需要过滤掉数值重复的节点，比如11-4和8-1。

从平方数出发自底向上：

由比已知目标数小的所有平方数出发，每层做一个组合加法，但是有一些地方需要处理：

遇到数值相等的节点，如1+4和4+1，跳过该节点。
在组合的时候遇到从一个数开始，加上它就会大于目标数，那么它之后的平方数都可以不做组合了，因为都比它大。

代码

自顶向下：

class Node{
    public int value;
    public int depth;
    public Node(int value,int depth){
        this.value = value;
        this.depth = depth;
    }
}

class Solution {
    public int numSquares(int n) {
        int mark[] = new int[n];
        if(n<4) return n;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(n,0));
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.value==0) return node.depth; 
            int sqrt = (int)Math.sqrt(node.value);
            for(int i = sqrt; i > 0 ; i--){
                if(mark[node.value-i*i]==0){
                    queue.offer(new Node(node.value-i*i,node.depth+1));
                    mark[node.value-i*i] = 1;
                }
            }

        }
        return -1;
    }
}

自底向上

class Node{
    public int value;
    public int depth;
    public Node(int value,int depth){
        this.value = value;
        this.depth = depth;
    }
}

class Solution {
    public int numSquares(int n) {
        Queue<Node> queue = new LinkedList<>();
        int a = (int)Math.sqrt(n);
        int[] mark = new int[n+1];
        for(int i = a;i>a/2;i--){
            queue.offer(new Node(i*i,1));
            mark[i*i] = 1;
        }

        while(!queue.isEmpty()){
            Node node = queue.poll();
            int value = node.value;
            if(value==n) return node.depth;
            for(int i = 1;i<=a;i++){
                if(value+i*i>n) break;
                if(mark[value+i*i]==1) continue;
                queue.offer(new Node(value+i*i,node.depth+1));
                mark[value+i*i] = 1;
            }
        }
        return -1;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode279-%e5%ae%8c%e5%85%a8%e5%b9%b3%e6%96%b9%e6%95%b0/