完全平方数

[JesseZhao1990]

/**
 * @param {number} n
 * @return {number}
 */
function node(val,step){
    this.val = val;
    this.step = step;
}

var numSquares = function(n) {
    var queue = [];
    var visited = {};
    
    queue.push(new node(n,0));
    visited[n] = true;
    
    while(queue.length>0){
        var front = queue[0].val;
        var step = queue[0].step;
        queue.shift();
        
        if(front===0) return step;
        
        for(var i=0;front-i*i>=0;i++){
            if(visited[front-i*i]!== true){
                queue.push(new node(front-i*i,step+1));
                visited[front-i*i]= true;
            }
        }
    }
    
};

思路：建模，整个问题转化为图论问题
从N到0的所有节点，如果某两个节点之间相差一个完全平方数，则连接一条边。此时我们得到了一个无权图，成功将问题转化为求这个无权图中从N到0的最短路径问题。

leetcode原题地址：https://leetcode-cn.com/problems/perfect-squares/description/