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

怼烎@ 2022-11-27 15:50 207阅读 0赞

## 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;
      }
    
    
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-279.完全平方数

目录题目思路回溯法动态规划动态规划(压缩) 题目来源 [279.完全平方数][279.] 题目思路

柔光的暖阳◎/ 2024年03月25日 20:21/ 0 赞/ 121 阅读

相关 Leetcode 279. 完全平方数

Leetcode 279. 完全平方数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.

墨蓝/ 2023年02月14日 03:06/ 0 赞/ 51 阅读

相关 279. 完全平方数(完全背包)

\\\ 解题思路一个典型的完全背包问题 \\\ 代码 class Solution { public: int numSquares(i

系统管理员/ 2023年01月12日 13:59/ 0 赞/ 208 阅读

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

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

怼烎@/ 2022年11月27日 15:50/ 0 赞/ 208 阅读

相关 279. 完全平方数

题目： [279. 完全平方数][279.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

你的名字/ 2022年11月25日 00:58/ 0 赞/ 210 阅读

相关 279. 完全平方数

2021-06-11 LeetCode每日一题链接：[https://leetcode-cn.com/problems/perfect-squares/][https_

女爷i/ 2022年10月06日 06:52/ 0 赞/ 224 阅读

相关 279. 完全平方数

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

心已赠人/ 2022年10月06日 05:42/ 0 赞/ 227 阅读

相关 LeetCode 279 完全平方数

https://leetcode-cn.com/problems/perfect-squares/ ![在这里插入图片描述][2f27a9f8cc0b4daeab65061

柔光的暖阳◎/ 2022年09月03日 10:24/ 0 赞/ 227 阅读

相关 leetcode 279 完全平方数

前言题目：[279. 完全平方数][279.] 参考题解：[完全平方数-代码随想录][-] -------------------- 提交代码完全背包问题

刺骨的言语ヽ痛彻心扉/ 2022年08月28日 03:52/ 0 赞/ 210 阅读

相关 LeetCode279——完全平方数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

偏执的太偏执、/ 2022年03月10日 07:24/ 0 赞/ 236 阅读