【LeetCode】【算法】279. 完全平方数

LeetCode 279. 完全平方数

题目描述

给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9

思路

和LeetCode 322.零钱兑换很类似,这里也是使用动态规划的思路求解。

  1. 创建dp动态数组,每个索引下标i表示组成值i最少需要几个完全平方数;
  2. 数组初始化:dp[0]=0;对于其他每个下标i,组成值i最少需要i个1(1是完全平方数),所以初始化就是让dp[i]=i;
  3. 嵌套循环填充dp数组,第一个for循环遍历从i~n,循环体内部求和为n的完全平方数的最少数量;
  4. 第二个for循环遍历的终止条件是i-j*j>=0,jj实际上就是完全平方数,j的遍历范围从1开始,每次+1,那么jj的结果就是从1,4,9,16…依次在各个完全平方数内变换。这一点和零钱兑换的那题很类似,实际上就是遍历不超过i的完全平方数(因为完全平方数超过i必不可能组成i,和零钱兑换中的if条件是类似的,如果你的硬币币值>目标金额的话,这个硬币也不可能被用于组成目标金额)
  5. 对于动态转移方程,求的是和为n的完全平方数的最少数量,故dp[i]=Math.min(dp[i],dp[i-j*j]+1),前面也就是不使用完全平方数j时候的结果,后面是使用完全平方数j的结果
  6. return dp[n];

代码

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1]; // dp数组中的每个下标i表示,组成值i完全平方数的最少数量// 填充dp数组for (int i = 1; i <= n; i++) {dp[i] = i; // 最坏的情况就是,该数由许多1组成,实际上这里设置成Integer.MAX_VALUE也可以for (int j = 1; i - j * j >= 0; j++){// 首先说明for循环的条件为什么是: i-j*j>=0,首先变换一下i>=j*j// j*j实际上就凑成了一个“完全平方数”,在这个for循环里,j的值从1开始,每次不断+1,那么j*j的值就是1,4,9,16...,每次都是完全平方数// 这里实际上就是“假设我们使用这个完全平方数”时// i-j*j中,我们想求i需要多少个完全平方数凑成// 也就是使用了这个完全平方数后的数(j*j是完全平方数,i-j*j是剩余的数值),剩余的数值最少需要由几个完全平方数凑成dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466531.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

云计算答案

情境一习题练习 一、选择题 1、在虚拟机VMware软件中实现联网过程&#xff0c;图中箭头所指的网络连接方式与下列哪个相关&#xff08; C &#xff09;。 A.仅主机模式 B.桥接 C.NAT D.嫁接 2、请问下图这个虚拟化架构属于什么类型&#xff08; A …

如何做好多项目进度管理

在同时管理多个项目时&#xff0c;重要的是要确保每个项目都能按时、按质完成。有效的时间管理、资源优化配置、持续的沟通和使用专业工具是关键要素。这些元素有助于维护项目的整体质量和效率&#xff0c;确保所有项目成员的责任和期望都明确无误。本文将深入探讨如何通过实践…

如何在vscode中安装git详细新手教程

一、安装git后点击vscode中的设置 今天教大家如何在VScode中编写代码后提交到git仓库&#xff0c;如果我们不想切换到git的命令行窗口&#xff0c;可以在VScode中配置git&#xff0c;然后就可以很方便快捷的把代码提交到仓库中。 二、在输入框中输入 git.path &#xff0c;再点…

使用Docker Compose构建多容器应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用Docker Compose构建多容器应用 引言 Docker Compose 简介 安装 Docker Compose 创建基本配置 运行多容器应用 查看服务状态 …

Python-利用tkinter库编写一个exe伪恶意程序文件(下)

前言 接着上篇所讲的&#xff0c;我们已经完成了源代码的准备&#xff0c;并将其储存在了function_1.py文件中。接下来我们将把function_1.py文件编写为相对应的exe文件。那么好&#xff0c;废话不多说&#xff0c;我们直接开始。&#xff08;温馨提示&#xff1a;由于整蛊的需…

java list使用基本操作

import java.util.ArrayList; import java.util.Collection; import java.util.Iterator;public class Main {public static void main(String[] args) {ArrayList list new ArrayList();list.add("张三");list.add("李四");list.add("王五");l…

【C/C++】strncpy函数的模拟实现

零.导言 之前我们学习了strncpy函数&#xff0c;不妨我们现在尝试模拟实现strncpy函数的功能。 一.实现strncpy函数的要点 strncpy函数是一种字符串函数&#xff0c;可以按字节拷贝字符类型的数组&#xff0c;因此我们自定义的模拟函数需要两个char类型的指针参数&#xff1b;…

ARM-8 定位发布版本 pstree 程序的 main 地址

逆向时如何找到main&#xff0c;如下&#xff1a; 1.readelf -h pstree ELF Header: Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 Class: ELF64 Data: 2s complement, little endian Versi…

履带机器人(一、STM32控制部分--标准库)

一、履带机器人整体逻辑框架 通过在PC端搭建上位机,使得在PC端可以给STM32发送控制指令并且接受STM32的状态信息。 通过RS485通信,使得STM32可以和电机进行通信,STM32发送启动、停止、转速、方向等指令,并接受电机返回的状态信息。 二、STM32逻辑框架 整体逻辑: 1、先…

数据库管理-第258期 23ai:Oracle Data Redaction(20241104)

数据库管理258期 2024-11-04 数据库管理-第258期 23ai&#xff1a;Oracle Data Redaction&#xff08;20241104&#xff09;1 简介2 应用场景与有点3 多租户环境4 特性与能力4.1 全数据编校4.2 部分编校4.3 正则表达式编校4.4 随机编校4.5 空值编校4.6 无编校4.7 不同数据类型上…

Rust重写万物之——从头开始编写浏览器引擎

一款用 Rust 编写的全新“轮子”最近备受关注—— 因不满大公司垄断,Gosub 项目团队用 Rust 从头开始编写了一个新的浏览器引擎,目前 star 数已超过 3k。 Gosub 项目的诞生是因为不少用户对当前的 Web 浏览器现状感到不满。 尽管市面上有许多浏览器可供选择,但其中大多数…

Elasticsearch-linux环境部署

本文主要介绍linux下elasticsearch的部署。通过在一台linux服务器中分别对elasticsearch-6.7.2版本&#xff0c;elasticsearch-7.3.0版本来进行安装&#xff0c;记录在安装elasticsearch-7.3.0版本时出现的异常情况&#xff0c;以及elasticsearch-head的安装。 基础环境 本机已…

mac crontab 不能使用问题简记

需要 crontab 有权限&#xff0c;如下截图设置 在访达上方【前往】-》【前往文件夹】输入/ 然后按 Command Shift . 显示隐藏文件&#xff0c;然后将 usr 放到左边栏 然后如下操作 系统设置中找到 隐私安全->完全访问磁盘 点击小锁头 点击号&#xff0c;将/usr/bin/c…

2款使用.NET开发的数据库系统

今天大姚给大家分享2款使用.NET开发且开源的数据库系统。 Garnet Garnet是一款由微软研究院基于.NET开源的高性能、跨平台的分布式缓存存储数据库&#xff0c;该项目提供强大的性能&#xff08;吞吐量和延迟&#xff09;、可扩展性、存储、恢复、集群分片、密钥迁移和复制功能…

基于java+SpringBoot+Vue的宠物咖啡馆平台设计与实现

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; Springboot mybatis Maven mysql5.7或8.0等等组成&#x…

书生第四期实训营基础岛——L1G2000 玩转书生「多模态对话」与「AI搜索」产品

基础任务 MindSearch使用示例 书生浦语使用示例 书生万象使用示例 进阶任务 问题&#xff1a;目前生成式AI在学术和工业界有什么最新进展&#xff1f; 回答截图&#xff1a; 知乎回答链接&#xff1a;目前生成式AI在学术和工业界有什么最新进展&#xff1f;

队列实现约瑟夫环(数据结构实验报告1)

目录 约瑟夫环问题 问题分析 完整代码 运行结果 约瑟夫环问题 实验题目&#xff1a;约瑟夫环问题&#xff1a;设编号为1&#xff0c;2&#xff0c;3&#xff0c;……&#xff0c;n的n(n>0)个人按顺时针方向围坐一圈&#xff0c;m为任意一个正整数。从第一个人开始顺时…

js例轮播图定时器版

要求 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name"viewport" content"widthdevice-width, ini…

基于SSD模型的路面坑洼检测系统,支持图像、视频和摄像实时检测【pytorch框架、python源码】

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; 基于SSD模型的路面坑洼检测系统&#xff0c;支持图像、视频和摄像实时检测【pytorch框架、python源码】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于SSD模型的路面坑洼检测系统是在 Py…

数据结构---二叉树(顺序结构),堆(上)

树 树的概念与结构 树是⼀种⾮线性的数据结构&#xff0c;它是由 n&#xff08;n>0&#xff09; 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;⽽叶朝下的。 PS 有⼀个特殊的结点&#xff…