```
import math
class Solution(object):
def numSquares(self, n):
queue = [n]
step = 0
while queue:
next = []
while queue:
start = queue.pop(0)
for i in range(int(math.sqrt(start)), 0, -1):
var = i * i
if var == start:
return step + 1
next.append(start - var)
step += 1
queue = next
public class Solution {
public int numSquares(int n) {
int step = 0;
Deque<Integer> queue = new LinkedList<>();
queue.offer(n);
Deque<Integer> next = new LinkedList<>();
while (!queue.isEmpty()) {
next.clear();
while (!queue.isEmpty()) {
int tmp = queue.poll();
for (int i = (int) Math.sqrt(tmp); i > 0; i--) {
if (tmp == i * i) return step + 1;
next.offer(tmp - i * i);
}
}
step++;
queue = new LinkedList<>(next);
}
return 0;
}
}
```