2019-05-23完全平方数

···
import java.util.*;

public class Code_bsf1完全平方数 {

/*这个题的整体思路是先对这个目标数开方找到这个数最大开平方数n

然后从目标数出发每次都减掉从 1 -- n的平方数(先把这些平方数放到一个集合中)

直到减到剩下的这个数已经存在这个集合中了就停止就可以得到结果

*/

public static int numSquares(int n) {

int tmp = (int)Math.sqrt(n);

int res = bfs(n, tmp);

return res;

}

public static int bfs(int n, int tmp) {

int step = 0;

Queue<Integer> q = new LinkedList<Integer>(); // 队列

Set<Integer> set = new HashSet<Integer>(); // 存放平方数的集合

q.offer(n); // 目标数

while(!q.isEmpty()) {

step++;

int size = q.size();

for(int i = 0; i < size; i++) {

int now = q.peek();

if(set.contains(now)) { // 如果这个队列中已经有这个数的平方了就return

return step;

}

for(int j = 1; j <= tmp; j++) {

int sum = j * j;

if(now == sum) {

return step; // 如果这个队列中已经有这个数的平方了就return

}

if(now == n) { // 当now还是目标数的时候将这些平方数存入set中

set.add(sum);

}

q.offer(now - sum); // 减掉平方数

}

q.poll();

}

}

return -1;

}

public static void main(String[] args) {

System.out.println(numSquares(13));

}

}