当前位置: 首页 > news >正文

【leetcode279】完全平方数,动态规划解法

原问题:给定一个非负整数n,如果把它视作一些完全平方数的和,那么最少需要多少个完全平方数?

这次学习到一个热心网友的解法:把问题转化兑换零钱问题,然后使用动态规划求解。
比如,给定 n=12, 那么我们可以列举出可能的完全平方数{1,4,9}。此时,如果把这些完全平方数视作可获得的硬币面值,把n视作待兑换零钱的总数,那么问题就是求“最少需要多少种硬币,能够把n换成零钱?如果兑换不成功,那么返回-1.”)

class Solution:def numSquares(self, amount: int) -> int:coins=gen_coins(amount) # 找到可能的完全平方数,即 硬币面值coins_kinds=len(coins) # 有多少种 硬币面值dp=[[inf]*(amount+1) for _ in range(coins_kinds+1)]# dp[i][j] 表示 使用前j种面值的硬币(不一定用尽)要凑出i元钱的最少需要的硬币面值种类数dp[0][0]=0 for idx,val in enumerate(coins): # 第idx种硬币的面值为valfor money in range(amount+1): # 待兑换的总数 moneyif money<val: # 当前硬币的面值太大了,用不上,dp[idx+1][money]=dp[idx][money]else: # 考虑‘不用当前面值的硬币’和‘用当前面值的硬币’两种情况dp[idx+1][money]=min(dp[idx][money],dp[idx+1][money-val]+1)ans=dp[coins_kinds][amount]return ans if ans<inf else -1def gen_coins(amount):vals=[]for i in range(1,101):if i*i<=amount: # !! 注意这里是<=vals.append(i*i)else:breakreturn vals

相关文章:

【leetcode279】完全平方数,动态规划解法

原问题&#xff1a;给定一个非负整数n&#xff0c;如果把它视作一些完全平方数的和&#xff0c;那么最少需要多少个完全平方数&#xff1f; 这次学习到一个热心网友的解法&#xff1a;把问题转化兑换零钱问题&#xff0c;然后使用动态规划求解。 比如&#xff0c;给定 n12, 那…...

Java 元素排序(数组、List 集合)

数组元素排序 升序 int[] array {3, 1, 4, 5}; Arrays.sort(array);// 升序排序 System.out.println(Arrays.toString(array)); //输出&#xff1a;[1, 3, 4, 5]降序 可以先将数组元素存入 List 集合&#xff0c;然后集合元素逆序&#xff0c;最后将集合元素写回原数组。&a…...

使用vite创建一个react18项目

一、vite是什么&#xff1f; vite 是一种新型前端构建工具&#xff0c;能够显著提升前端开发体验。它主要由两部分组成&#xff1a; 一个开发服务器&#xff0c;它基于原生 ES 模块提供了丰富的内建功能&#xff0c;如速度快到惊人的模块热更新&#xff08;HMR&#xff09;。 …...

子集(迭代)(leetcode 78)

核心逻辑&#xff1a; 根据子数组包含的元素个数迭代&#xff1a; 现有子集的基础上通过添加这个新元素来翻倍子集的数量 f(n)2f(n−1) vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;int i,j,k;ans.p…...

汽车疲劳测试试验平台技术要求(北重厂家)

汽车疲劳测试试验平台技术要求通常包括以下几个方面&#xff1a; 车辆加载能力&#xff1a;测试平台需要具备足够的承载能力&#xff0c;能够同时测试多种车型和不同重量的车辆。 动力系统&#xff1a;测试平台需要具备稳定可靠的动力系统&#xff0c;能够提供足够的力和速度来…...

Redis -- 缓存雪崩问题

缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机&#xff0c;导致大量请求到达数据库&#xff0c;带来巨大压力。 可能原因 : 同一时间大量的key到期 ; 解决方案&#xff1a; 给不同的Key的TTL添加随机值 利用Redis集群提高服务的可用性 给缓存业务添加降…...

【ARM 嵌入式 C 文件操作系列 20 -- 文件删除函数 remove 详细介绍】

请阅读【嵌入式开发学习必备专栏 】 文章目录 文件删除函数 remove 文件删除函数 remove 在 C 语言中&#xff0c; 可以使用 remove 函数来删除一个文件&#xff0c;但在删除之前 可能想确认该文件是否存在。 可以使用 stat 函数来检查文件是否存在。 以下是如何实现这个功能…...

LeetCode刷题之31.下一个排列

文章目录 1. 题目2.分析3.解答3.1 先排序&#xff0c;后交换3.2 先交换&#xff0c;后排序 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3…...

【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(九)- 向量定点算术指令

1. 引言 以下是《riscv-v-spec-1.0.pdf》文档的关键内容&#xff1a; 这是一份关于向量扩展的详细技术文档&#xff0c;内容覆盖了向量指令集的多个关键方面&#xff0c;如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量…...

【Java网络编程】IP网络协议与TCP、UDP网络传输层协议

1.1、IP协议 当应用层的数据被封装后&#xff0c;想要将数据在网络上传输&#xff0c;数据究竟要被发往何处&#xff0c;又该如何精准的在网络上定位目标机器&#xff0c;此时起到关键作用的就是“IP协议”。IP协议的作用在于把各种数据包准确无误的传递给目标方&#xff0c;其…...

C# 分布式自增ID算法snowflake(雪花算法)

文章目录 1. 概述2. 结构3. 代码3.1 IdWorker.cs3.2 IdWorkerTest.cs (测试) 1. 概述 分布式系统中&#xff0c;有一些需要使用全局唯一ID的场景&#xff0c;这种时候为了防止ID冲突可以使用36位的UUID&#xff0c;但是UUID有一些缺点&#xff0c;首先他相对比较长&#xff0c…...

commonJS和esModule的应用

commonJS commonJS规范的核心变量是&#xff1a;exports&#xff0c;module.exports&#xff0c;require exports 和 module.exports可以负责模块的导出require 负责模块的导入 module.exports 导出方案&#xff1a; const name yx const age 18// 1 导出方案 module.exp…...

(十一)RabbitMQ及SpringAMQP

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;…...

STM32 M3内核寄存器概念

内容主要来自<<M3内核权威指南>> 汇编程序中的最低有效位&#xff08;Least Significant Bit&#xff09;。LSB是二进制数中最右边的位&#xff0c;它代表了数值中的最小单位。在汇编程序中&#xff0c;LSB通常用于表示数据的最小精度或者作为标志位。 ---------…...

SQL语句的编写

##创建用户-建表建库 #创建一个用户名为 feng&#xff0c;允许从任何主机 % 连接&#xff0c;并使用密码 sc123456 进行身份验证的用户。 rootTENNIS 16:33 scmysql>create user feng% identified by sc123456; Query OK, 0 rows affected (0.04 sec) #创建一个名为fen…...

Lecture 1~3 About Filter

文章目录 空间域上的滤波器- 线性滤波器盒状滤波器Box Filter锐化Sharpening相关运算 vs. 卷积运算 Correlation vs. Convolution - 非线性滤波器高斯滤波器Gaussian filter - 实际问题- 纹理texture 频域上的滤波器 滤波的应用- 模板匹配- 图像金字塔 空间域上的滤波器 图像…...

配置vscode链接linux

1.安装 remote SSH 2.按F1 ssh ljh服务器公网ip 3. 选择保存远端host到本地 某位置 等待片刻后 4. 切换到远程资源管理器中 应该可以看到一台电脑&#xff0c;右键在当前窗口链接&#xff0c;输入你的服务器用户密码后电脑变绿说明远程连接成功 5.一定要登陆上云服务器后再…...

论文阅读——MVDiffusion

MVDiffusion: Enabling Holistic Multi-view Image Generation with Correspondence-Aware Diffusion 文生图模型 用于根据给定像素到像素对应关系的文本提示生成一致的多视图图像。 MVDiffusion 会在给定任意每个视图文本的情况下合成高分辨率真实感全景图像&#xff0c;或将…...

Linux中的网络命令深度解析与CentOS实践

Linux中的网络命令深度解析与CentOS实践 在Linux系统中,网络命令是管理和诊断网络问题的关键工具。无论是网络管理员还是系统开发者,熟练掌握这些命令都是必不可少的。本文将深入探讨Linux中常用的网络命令,并以CentOS为例,展示这些命令的具体应用。 一、ping命令 ping命…...

nginx配置实例(反向代理)

目录 一、目标-反向代理实现效果 二、安装tomcat 三、配置nginx服务 四、配置反向代理 一、目标-反向代理实现效果 访问过程分析&#xff1a; 二、安装tomcat 1、安装jdk环境 新建/export/server目录 解压jdk 查看是否解压成功 配置jdk软连接 进入jdk的bin目录中&#x…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...