6. 完全平方数

// 一个size的循环就是一层的遍历，在这一层只拿最右边的结点 let front = queue.shift();

if(front.right) queue.push(front.right);

if(front.left) queue.push(front.left);

} }

return res;

};

6. 完全平方数

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

示例:

输入: n = 12 输出: 3

解释: 12 = 4 + 4 + 4.

思路

这一题其实最容易想到的思路是动态规划，我们放到后面专门来拆解。实际上用队列进行图的建模，也是可以顺利地用广度优先遍历的方式解决的。

看到这个图，你可能会有点懵，我稍微解释一下你就明白了。

在这个无权图中，每一个点指向的都是它可能经过的上一个节点。举例来说，对 5 而言，可能是 4 加上

Talk is cheap, show me your code. 我们接下来来一步步实现这个寻找的过程。

实现

接下来我们来实现第一版的代码。

/**

• @param {number} n
• @return {number}

*/ var numSquares = function(n) {

let queue = [];

queue.push([n, 0]);

while(queue.length) { let [num, step] = queue.shift();

for(let i = 1; ; i ++) { let nextNum = num - i * i;

if(nextNum < 0) break;

// 还差最后一步就到了，直接返回 step + 1 if(nextNum == 0) return step + 1;

queue.push([nextNum, step + 1]);

} }

// 最后是不需要返回另外的值的，因为 1 也是完全平方数，所有的数都能用 1 来组合 };

这个解法从功能上来讲是没有问题的，但是其中隐藏了巨大的性能问题

那为什么会出现这样的问题？

出就出在这样一行代码:

queue.push([nextNum, step + 1]);

只要是大于 0 的数，统统塞进队列。要知道 2 - 1 = 1， 5 - 4 = 1， 9 - 8 = 1 ......这样会重复非常多的 1, 依次类推，也会重复非常多的2, 3等等等等。

这样大量的重复数字不仅仅消耗了更多的循环次数，同时也造成更加巨大的内存空间压力。

因此，我们需要对已经推入队列的数字进行标记，避免重复推入。改善代码如下:

var numSquares = function(n) { let map = new Map();

let queue = [];

queue.push([n, 0]);

map.set(n, true);

while(queue.length) { let [num, step] = queue.shift();

for(let i = 1; ; i++) {