[LeetCode][JavaScript]Perfect Squares

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

https://leetcode.com/problems/perfect-squares/

一个数如果是perfect square，这个数可以拆成若干个平方数相加，求最少需要几个平方数，隐含的意思是一定有解，因为有1在。

因为要找最少需要几个平方数，选择用BFS，如果找到了结果，搜索的层数就是答案。

首先找所有小于n的平方数，放入prime数组中。

开一个队列，一开始队列中只有n，每轮遍历将队列中所有的数，减去所有的平方数，把减下来的数继续放入队列中，在下一轮的遍历使用。下图就是BFS的过程。

如果减到最后结果是0，说明找到了答案。

使用哈希表(也可以是set)代替队列，因为有很多重复的数字，不去重一定会超时。

 1 /**
 2  * @param {number} n
 3  * @return {number}
 4  */
 5 var numSquares = function(n) {
 6     var prime = [], queue = {},
 7         sqrt = Math.floor(Math.sqrt(n));
 8     for(var i = 1; i <= sqrt; i++)
 9         prime.push(i * i);
10     queue[n] = true;
11     return bfs(queue, 1);
12 
13     function bfs(queue, depth){
14         var i, j, newQueue = {}, tmp;
15         for(i in queue){
16             for(j = 0; j < prime.length; j++){
17                 tmp = Math.floor(i) - prime[j];
18                 if(tmp === 0)
19                     return depth;
20                 if(tmp < 0)
21                     break;
22                 if(tmp > 0)
23                     newQueue[tmp] = true;
24             }
25         }
26         return bfs(newQueue, depth + 1);
27     }
28 };

稍微修改一下代码，可以知道n是由哪个数相加而来。

 1 /**
 2  * @param {number} n
 3  * @return {number}
 4  */
 5 var numSquaresDetail = function(n) {
 6     var prime = [], queue = {},
 7         sqrt = Math.floor(Math.sqrt(n));
 8     for(var i = 1; i <= sqrt; i++)
 9         prime.push(i * i);
10     queue[n] = [];
11     return bfs(queue, 1).sort(sorting).join(' + ');
12 
13     function bfs(queue){
14         var i, j, newQueue = {}, tmp, arr;
15         for(i in queue){
16             for(j = 0; j < prime.length; j++){
17                 tmp = Math.floor(i) - prime[j];
18                 arr = queue[i].slice(0);
19                 arr.push(prime[j]);
20                 if(tmp === 0)
21                     return arr;
22                 if(tmp < 0)
23                     break;
24                 if(tmp > 0)                
25                     newQueue[tmp] = arr;
26             }
27         }
28         return bfs(newQueue);
29     }
30     function sorting(a, b){
31         return a - b;
32     }
33 };