当前位置: 首页 > 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…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

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

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

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...