Leetcode面试经典150题-322.零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins =[1, 2, 5], amount =11输出:3解释:11 = 5 + 5 + 1
示例 2:
输入:coins =[2], amount =3输出:-1
示例 3:
输入:coins = [1], amount = 0 输出:0
提示:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
这个题很容易就写成二维的动态规划了,使用一维动态规划需要理清思路,其他的就不多说了,上代码,看不懂的请留言或者私信,收到第一时间解答
class Solution {/**本题是零钱兑换系列问题,思路是动态规划,边解题边解释思路吧 */public int coinChange(int[] coins, int amount) {/**如果只有一种货币,能除尽就直接返回,除不尽返回-1 */if(coins.length == 1) {return amount % coins[0] == 0? amount / coins[0] : -1;}/**如果不止一个,使用动态规划进行解题,先定义动态规划数组dp, dp[i]的含义是i这个amount最少由多少个硬币凑成我们从小金额到大金额进行循环,比如我们的硬币分别是1,2,5,dp[1]=1 dp[2]=1 dp[3]=2dp[4]=Math.min(dp[4-1]+1, dp[4-2]+1)=2dp[5]=Math.min(dp[5-1]+1, dp[5-2]+1, dp[5-5]+1)括号里的三个分别表示凑够了4再加个1元,凑够了3再加一张2元,凑够了0再加一张5元...dp[11]= Math.min(dp[11-1]+1, dp[11-2]+1,dp[11-5]+1)*/int[] dp = new int[amount + 1];/**先都设置为最大值 */Arrays.fill(dp, Integer.MAX_VALUE);/**0这个金额0个硬币就能凑出来,所以dp[0]=0 */dp[0] = 0;/**给硬币数组排个序 */Arrays.sort(coins);/**从1到amount进行遍历 */for(int curAmount = 1; curAmount <= amount ; curAmount++) {for(int i = 0; i < coins.length; i++) {/**如果小于0了,我们dp数组就越界了,而且负数不可能由任何树组成就算它存在也应该是最大值 */if(curAmount - coins[i] < 0) {break;}dp[curAmount] = Math.min(dp[curAmount], dp[curAmount-coins[i]] == Integer.MAX_VALUE? Integer.MAX_VALUE : dp[curAmount-coins[i]] + 1);}}return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];}
}
时间复杂度肯定是最低了,表现一般般,凑活这看吧

相关文章:
Leetcode面试经典150题-322.零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...
python17_len()函数
len()函数 A B "" C "hello world" D 18 E 18def len_test(s):try:# 尝试计算字符串的长度length len(s)return lengthexcept TypeError:# 如果不是字符串,则返回 None 或者提示错误return Noneif __name__ "__main__":# 单…...
车视界系统小程序的设计
管理员账户功能包括:系统首页,个人中心,汽车品牌管理,汽车颜色管理,用户管理,汽车信息管理,汽车订单管理系统管理 微信端账号功能包括:系统首页,汽车信息,我…...
SQLCMD命令行工具导入数据并生成对应的日志文件
SQLCMD是一个命令行工具,专门用于在Microsoft SQL Server数据库上运行SQL脚本和管理任务。它提供了一种交互式和自动化的方式来执行SQL命令和脚本,并允许用户与SQL Server数据库进行高效的交互。以下是关于SQLCMD的详细介绍: 主要功能 执行SQL脚本: SQLCMD可以执行包含SQL…...
tauri中加载本地文件图片或者下载网络文件图片后存储到本地,然后通过前端页面展示
有一个需求是需要将本地上传的文件或者网络下载的文件存储到本地,并展示在前端页面上的。其实如果只是加载本地文件,然后展示还是挺简单的,可以看我的文章:tauri程序加载本地图片或者文件在前端页面展示-CSDN博客 要想实现上述需…...
QSqlDatabase在多线程中的使用
Qt中多线程使用数据库_qt数据库管理类支持多数据库,多线程-CSDN博客 1. 代码: #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPushButton> #include <QSqlDatabase> #include <QSqlQuery> #include <QSqlError>…...
【无人机设计与控制】Multi-UAV|多无人机多场景路径规划算法MATLAB
摘要 本研究探讨了多无人机路径规划问题,提出了三种不同算法的对比分析,包括粒子群优化(PSO)、灰狼优化(GWO)和鲸鱼优化算法(WOA)。利用MATLAB实现了多场景仿真实验,验证…...
Visual Studio C# 编写加密火星坐标转换
Visual Studio C# 编写加密火星坐标转换 1、WGS84坐标转GCJ02火星坐标2、GCJ02火星坐标转WGS84坐标(回归计算)3、GCJ02火星坐标转BD09百度坐标4、BD09百度坐标转GCJ02火星坐标(回归计算)5、坐标公共转换类6、地图显示7、程序简单界…...
微服务-流量染色
1. 功能目的 通过设置请求头的方式将http请求优先打到指定的服务上,为微服务开发调试工作提供便利 请求报文难模拟:可以直接在测试环境页面上操作,流量直接打到本地IDEA进行debug请求链路较长:本地开发无需启动所有服务…...
C语言实现 操作系统 经典的进程同步问题(2)
哲学家进餐问题 哲学家进餐问题是一个经典的同步问题,涉及多个哲学家试图同时用餐,但每个哲学家左右两边只有一把叉子。为了避免死锁和饥饿,可以使用记录型信号量(也称为计数信号量)来管理叉子的使用。 1、利用记录型…...
有效的字母异位词【字符串哈希】
题目 题解: 1.排序: #include<algorithm>class Solution{public:bool isAnagram(string s,string t){sort(s.begin(),s.end());sort(t.begin(),t.end());return st;} } 时间复杂度O(nlogn) 2.哈希表 #include<algorithm>int hash1[100]; …...
如何选择与运用工具提升工作效率的秘密指南
一、引言 ---- 在当今这个信息爆炸的时代,编程工具的选择对于开发者的工作效率至关重要。从智能的代码编辑器到强大的版本控制工具,再到那些能让我们事半功倍的自动化脚本,每一款工具都有其独特的优势和价值。那么,哪款编程工具…...
Spring系列 AOP实现过程
文章目录 实现原理EnableAspectJAutoProxyAnnotationAwareAspectJAutoProxyCreator 代理创建过程wrapIfNecessarygetAdvicesAndAdvisorsForBeanfindCandidateAdvisorsfindAdvisorsThatCanApply createProxy AspectJ注解处理代理调用过程 实现原理 本文源码基于spring-aop-5.3.…...
C语言 getchar 函数完全解析:掌握字符输入的关键
前言 在C语言中,getchar 是一个非常实用的函数,用于从标准输入流(通常是键盘)读取单个字符。这对于处理文本输入非常有用,尤其是在需要逐个字符处理的情况下。本文将深入探讨 getchar 函数的用法和特点,并…...
Docker安装mysql8并配置主从复制
1. 安装mysql8 1.1 新增挂载文件 # 新增mysql挂载文件夹 mkdir -p /root/docker/mysql/m01/log mkdir -p /root/docker/mysql/m01/data mkdir -p /root/docker/mysql/m01/conf1.2 新增mysql配置文件 # 新增mysql配置文件 cd /root/docker/mysql/m01/conf vim my.cnf # 下面是…...
快手:数据库升级实践,实现PB级数据的高效管理|OceanBase案例
本文作者:胡玉龙,快手技术专家 快手在较初期采用了OceanBase 3.1版本成功替换了多个核心业务、数百套的MySQL集群。至2023年,快手的数据量已突破800TB大关,其中最大集群的数据量更是达到了数百TB级别。为此,快手将数据…...
基于Node.js+Express+MySQL+VUE实现的计算机毕业设计共享单车管理网站
单车信息选择骑行 骑行状态留言公告/springboot/javaWEB/J2EE/MYSQL数据库/vue前后分离小程序 目录 功能图 界面展示 开发目标 开发背景意义 开发意义 开发目的 项目概述 技术选型与理由 系统设计与功能实现 项目可执行性分析 系统架构需求 性能需…...
人工智能辅助的神经康复
人工智能辅助的神经康复是通过应用人工智能(AI)技术来改善神经系统损伤患者的康复过程。此领域结合了深度学习、数据分析和机器人技术,旨在提升康复效果、个性化治疗方案和监测进展。以下是该领域的关键组成部分和应用: 1. 康复评…...
KKT实际运用 -MATLAB
FMINCON函数可以很方便的求出:fun:目标函数,即需要最小化的函数,输入参数为向量x,输出为标量f(x)。x0:初始点,即求解过程的起始点,可以是标量、向量或矩阵。A和b:线性不等…...
php在线相册
1、将静态页面效果完成 解压到www里 整个数据 暂时是错误的 建立连接密码为root 运行sql文件 右键根目录刷新 刷新后成功 开始 测试 如果需要上传照片,点击创建相册,选择上传文件,选择文件后退出 导入alumbenew2 2.提交表单方式 3.利用ph…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
