原题
给定正整数 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/
