本题练习队列，以及BFS。
文内代码全部采用JAVA语言。

题目

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

测试用例

示例 1:

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

示例 2:

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

个人解法

广度优先搜索（BFS），用队列来做。但是这道题麻烦的地方在于，不只是要找到target，还要记录来时的路径上的所有数据的和值。这里将n的值作为根节点，设置两条队列，一条队列存放完全平方数的值，一条队列存放剩余值（上一个节点-当前节点的差值）。例如n=7时，队列queuenum存放下一个完全平方数4,1，并在minus队列里存放当前的剩余值7-4=3和7-1=6，以此类推，直到minus队列里出现0。另外需要注意，当minus得到负值，说明该路径不能满足要求，不加入队列。

nextsquare是寻找邻居节点的构造函数，寻找比当前数小的所有完全平方数，形成list。

执行用时: 342 ms, 在Perfect Squares的Java提交中击败了11.88% 的用户。

class Solution {
        public int numSquares(int n) {
    	Queue<Integer> queuenum=new LinkedList<Integer>();//完全平方数队列
    	Queue<Integer> minus=new LinkedList<Integer>();//总数-当前完全平方数，得到0时结束
    	int sum=0;
    	int step=0;
    	queuenum.add(n);
    	minus.add(n);//总数是跟节点
    	while (true) {
			int size=queuenum.size();
			for (int i = 0; i < size; i++) {
				int curSnum=queuenum.peek();
				int curMin=minus.peek();
				if (curMin==0) {
					return step;
				}
				List<Integer> neib=nextsquare(curSnum);
				Iterator<Integer> it=neib.iterator();
				while (it.hasNext()) {
					int a=(Integer)it.next();
					if (curMin-a>=0) {
						queuenum.offer(a);
						minus.add(curMin-a);
					}
				}
				queuenum.poll();
				minus.poll();
			}
			step++;
		}
    }
    
    public List<Integer> nextsquare(int n) {
    	List<Integer> ans=new ArrayList<>();
    	double a=Math.ceil(Math.sqrt(n));
    	for (int i = (int)a; i >= 1; i--) {
    		ans.add((int)Math.pow(i, 2));

    	}
    	return ans;
    }
}

最快解法

效率不理想，围观了最快的几个解法之后，发现并不是采用BFS的思路，而是四平方和定理。
原谅我不是很想了解这个数学定理。。。。

四平方和定理说明：每个正整数，均可表示为4个整数的平方和。因此结果只有1,2,3,4，四种可能。满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足
$n=4^a \times (8\times b+7)$n=4a×(8×b+7)
我们首先将输入的n迅速缩小。然后我们再判断，这个缩小后的数是否可以通过两个平方数的和或一个平方数组成，不能的话我们返回3，能的话我们返回平方数的个数。

class Solution {
    //Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
    //结果只有1,2,3,4，四种可能。
    //推论：满足四数平方和定理的数n（必须满足由四个数构成），必定满足 n=4^a*(8^b+7)
    public int numSquares(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) // 满足推论 说明由4个完全平方数构成
            return 4;
        int a = 0;
        while (a * a <= n) {
            // 判断这个缩小后的数是否可以通过两个平方数的和或一个平方数组成
            int b = (int) (Math.sqrt((n - a * a)));// 如果n=a^2 那么b=0 
            // if (a * a == n)
            // return 1;
            if (a * a + b * b == n)
                //返回 a、b中非0的个数和
                return (a != 0 ? 1 : 0) + (b != 0 ? 1 : 0); 
            a += 1;
        }
        return 3;
    }
    
}