279. 完全平方数（JS实现）

1 题目

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

链接：https://leetcode-cn.com/problems/perfect-squares

2 思路

我们先计算可能的平方数，然后广度优先遍历构建一颗树，当找到叶子节点时，返回当前树的深度即可

3代码

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {

  const squares = [];
  for (let i=1; i<=Math.sqrt(n); i++) {
    squares.push(i * i);
  }

  let numSet = new Set();
  numSet.add(n);

  let level = 0;
  while (numSet.size > 0) {
      level++;
      let nextSet = new Set();      //每层的节点
      for (let num of numSet) {
        for (let squareNum of squares) {
            if (num === squareNum) {    //找到叶子节点
                return level;
            } else if (num < squareNum) {
                break;
            } else {
                nextSet.add(num - squareNum);
            }
        } 
      }
      numSet = nextSet;
  }


};