···
import java.util.*;
public class Code_bsf1完全平方數(shù) {
/*這個(gè)題的整體思路是先對這個(gè)目標(biāo)數(shù)開方找到這個(gè)數(shù)最大開平方數(shù)n
然后從目標(biāo)數(shù)出發(fā)每次都減掉從 1 -- n的平方數(shù)(先把這些平方數(shù)放到一個(gè)集合中)
直到減到剩下的這個(gè)數(shù)已經(jīng)存在這個(gè)集合中了就停止就可以得到結(jié)果
*/
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>(); // 隊(duì)列
Set<Integer> set = new HashSet<Integer>(); // 存放平方數(shù)的集合
q.offer(n); // 目標(biāo)數(shù)
while(!q.isEmpty()) {
step++;
int size = q.size();
for(int i = 0; i < size; i++) {
int now = q.peek();
if(set.contains(now)) { // 如果這個(gè)隊(duì)列中已經(jīng)有這個(gè)數(shù)的平方了就return
return step;
}
for(int j = 1; j <= tmp; j++) {
int sum = j * j;
if(now == sum) {
return step; // 如果這個(gè)隊(duì)列中已經(jīng)有這個(gè)數(shù)的平方了就return
}
if(now == n) { // 當(dāng)now還是目標(biāo)數(shù)的時(shí)候?qū)⑦@些平方數(shù)存入set中
set.add(sum);
}
q.offer(now - sum); // 減掉平方數(shù)
}
q.poll();
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(numSquares(13));
}
}
