【测试岗】手撕代码 - 零钱兑换
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
题解
from math import infdef min_coins(coins, amount):# 创建一个数组来保存每个金额所需的最少硬币数,初始化为无穷大dp = [float('inf')] * (amount + 1)# 0金额所需硬币数为0dp[0] = 0# 遍历每个金额直到目标金额for i in range(1, amount + 1):# 遍历每种硬币for coin in coins:# 如果当前硬币面值小于等于当前金额if coin <= i:# 更新当前金额所需的最少硬币数dp[i] = min(dp[i], dp[i - coin] + 1)# 如果目标金额无法组成,则返回-1,否则返回最少硬币数return dp[amount] if dp[amount] != float('inf') else -1print(min_coins([1, 2, 5], 11))
print(min_coins([2], 3))
print(min_coins([1], 0))
1. 题目理解
我们需要用给定的硬币面额(coins)来凑成一个指定的总金额(amount)。目标是找到所需的最少硬币数量。如果无法凑成指定金额,返回 -1。题目允许使用的硬币数量是无限的。
2. 代码思路
这是一个经典的动态规划问题,目标是通过选择不同的硬币面额,最小化硬币数量以凑成给定金额。动态规划的思想是通过构建一个数组
dp,记录凑成每个金额所需的最少硬币数,从而自底向上地解决问题。具体步骤如下:
- 初始化动态规划数组
dp:
dp[i]表示凑成金额i所需的最少硬币数。首先我们将所有金额的值初始化为一个较大的数(如无穷大),表示暂时无法凑成这个金额。- 特别地,
dp[0] = 0,因为凑成金额 0 所需的硬币数是 0。
- 遍历所有的金额 i:
- 对于每个金额
i,我们尝试每一种硬币面额coin,如果当前硬币面额小于等于i,则通过状态转移方程更新dp[i]的值。- 状态转移方程为:
dp[i] = min(dp[i], dp[i - coin] + 1),其中dp[i - coin]表示减去一个当前硬币后剩余金额的最优解。
- 结果判断:
- 当遍历完所有金额后,检查
dp[amount]的值。如果它仍然是无穷大,表示无法凑成该金额,返回 -1;否则,返回dp[amount],即凑成amount所需的最少硬币数。3. 算法分析
时间复杂度:
- 内层循环遍历
coins,外层循环遍历amount,因此时间复杂度为 O(amount * n),其中n是硬币的种类数。空间复杂度:
- 由于我们使用了一个大小为
amount + 1的数组来存储每个金额的最少硬币数,因此空间复杂度为 O(amount)。
相关文章:
【测试岗】手撕代码 - 零钱兑换
322. 零钱兑换 题目描述 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种…...
菱形继承的类对父类的初始化、组合、多态、多态的原理等的介绍
文章目录 前言一、菱形继承的类对父类的初始化二、组合三、 多态1. 构成多态2. 虚函数3. 虚函数的重写4. 虚函数重写的两个例外1. 协变2. 析构函数的重写 5. C11 final 和 override1. final2. override 6. 设计不想被继承的类7. 重载、覆盖(重写)、 隐藏…...
React Native 在 build 的时候如果出现 `babel.config.js` 配置文件的错误
React Native 在 build 的时候如果出现以下错误, 就是 babel.config.js 配置文件的错误. Showing Recent Issues node:internal/process/promises:289triggerUncaughtException(err, true /* fromPromise */);^Error: .plugins[0][1] must be an object, false, or undefineda…...
【Linux】包管理器、vim详解及简单配置
🚀个人主页:小羊 🚀所属专栏:Linux 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言一、包管理器1.1 apt1.2 yum 二、Linux编辑器——vim2.1 vim的三种模式2.2 vim普通模式常用命令2.2.1 移动…...
AVL树实现
1.AVL的概念 1.AVL树属于二叉搜索树的一种,但它不同与普通的二叉搜索树还具有以下的性质: 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的,所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概…...
初始MYSQL数据库(6)—— 事务
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏: MYSQL 目录 事务的概念 事务的ACID特性 使用事务 查看支持事务的存储引擎 事务的语法 保存点 自动/手动提交事务 事务的隔离性和…...
0基础学习PyTorch——GPU上训练和推理
大纲 创建设备训练推理总结 在《Windows Subsystem for Linux——支持cuda能力》一文中,我们让开发环境支持cuda能力。现在我们要基于《0基础学习PyTorch——时尚分类(Fashion MNIST)训练和推理》,将代码修改成支持cuda的训练和推…...
这款免费工具让你的电脑焕然一新,专业人士都在用
HiBit Uninstaller 采用单一可执行文件的形式,无需复杂的安装过程,用户可以即刻开始使用。这种便捷性使其成为临时使用或紧急情况下的理想选择。尽管体积小巧,但其功能却异常强大,几乎不会对系统性能造成任何负面影响。 这款工具的一大亮点是其多样化的功能。它不仅能够常规卸…...
Java高级Day52-BasicDAO
138.BasicDao 基本说明: DAO:data access object 数据访问对象 这样的通用类,称为 BasicDao,是专门和数据库交互的,即完成对数据库(表)的crud操作 在BasicDao 基础上,实现一张表对应一个Dao,…...
【OceanBase 诊断调优】—— SQL 诊断宝典
视频 OceanBase 数据库 SQL 诊断和优化:https://www.oceanbase.com/video/5900015OB Cloud 云数据库 SQL 诊断与调优的应用实践:https://www.oceanbase.com/video/9000971SQL 优化:https://www.oceanbase.com/video/9000889阅读和管理SQL执行…...
微服务Redis解析部署使用全流程
目录 1、什么是Redis 2、Redis的作用 3、Redis常用的五种基本类型(重要知识点) 4、安装redis 4.1、查询镜像文件【省略】 4.2、拉取镜像文件 4.3、启动redis并设置密码 4.3.1、修改redis密码【可以不修改】 4.3.2、删除密码【坚决不推荐】 5、S…...
C++之STL—常用排序算法
sort (iterator beg, iterator end, _Pred) // 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词 random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调…...
【驱动】地平线X3派:备份与恢复SD卡镜像
1、备份镜像 1.1 安装gparted GParted是硬盘分区软件GNU Parted的GTK+图形界面前端,是GNOME桌面环境的默认分区软件。 GParted可以用于创建、删除、移动分区,调整分区大小,检查、复制分区等操作。可以用于调整分区以安装新操作系统、备份特定分区到另一块硬盘等。 在Ubun…...
【C++报错已解决】std::ios_base::failure
🎬 鸽芷咕:个人主页 🔥 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 专栏介绍 在软件开发和日常使用中,BUG是不可避免的。本专栏致力于为广大开发者和技术爱好者提供一个关于BUG解决的经…...
matlab入门学习(四)多项式、符号函数、数据统计
一、多项式 %多项式(polynomial)%创建 p[1,2,3,4] %系数向量,按x降幂排列,最右边是常数(x的0次幂) f1poly2str(p,x) %系数向量->好看的字符串 f x^3 2 x^2 3 x 4(不能运算的式子…...
leetcode621. 任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表,用字母 A 到 Z 表示,以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成,但有一个限制:两个 相同种类 的任务之间必须有长度为 n 的冷却时…...
Spark 的 Skew Join 详解
Skew Join 是 Spark 中为了解决数据倾斜问题而设计的一种优化机制。数据倾斜是指在分布式计算中,由于某些 key 具有大量数据,而其他 key 数据较少,导致某些分区的数据量特别大,造成计算负载不均衡。数据倾斜会导致个别节点出现性能…...
讯飞星火编排创建智能体学习(一)最简单的智能体构建
目录 开篇 智能体的概念 编排创建智能体 创建第一个智能体 编辑 大模型节点 测试与调试 开篇 前段时间在华为全联接大会上看到讯飞星火企业级智能体平台的演示,对于拖放的可视化设计非常喜欢,刚开始以为是企业用户才有的,回来之后查…...
mac-m1安装nvm,docker,miniconda
1.安装minicondaMAC OS(M1)安装配置miniconda_mac-mini m1 conda-CSDN博客 2.安装nvm(用第二个方法)Mac电脑安装nvm(node包版本管理工具)-CSDN博客 3.安装docker dmg下载链接docker-toolbox-mac-docker-for-mac安装包下载_开源镜像站-阿里云 教程MacOS系…...
STM32F407之Flash
寄存器分类 一般寄存器分为只读存储器 (ROM) 随机存储器(RAM) 只读存储器 只读存储器也被称为ROM 在正常工作时只能读不能写。 只读存储器经历的阶段 ROM->PROM->EPROM->EEPROM ->Flash 优点:掉电不丢失,解构简单 缺点:只适…...
OpenClaw人人养虾:密钥管理
Gateway 提供安全的密钥管理(Secrets Management)功能,用于加密存储 API Key、Token 等敏感凭证,避免在配置文件中暴露明文。为什么需要密钥管理明文风险将 API Key 直接写在配置文件中存在严重安全风险:配置文件可能被…...
终极指南:如何参与Carbonyl开源终端浏览器项目贡献
终极指南:如何参与Carbonyl开源终端浏览器项目贡献 【免费下载链接】carbonyl Chromium running inside your terminal 项目地址: https://gitcode.com/gh_mirrors/ca/carbonyl Carbonyl是一个创新的开源项目,它让Chromium浏览器能够在终端中运行…...
基础知识:理解虚拟资产 / 数字商品 / 实用代币 / 稳定币 / 资产支持代币 / 数字收藏品 / 数字证券
比特币等虚拟资产全景与深度解析:超越“数字货币”的多元生态比特币等虚拟资产的世界,远比“一种数字货币”要丰富和复杂得多。理解它的第一步,就是先认识这个大家族里都有哪些成员。为了帮你建立清晰的概念,我们可以把虚拟资产看…...
Z-Image-Turbo-辉夜巫女完整指南:模型文件结构解析、LoRA注入位置与安全校验
Z-Image-Turbo-辉夜巫女完整指南:模型文件结构解析、LoRA注入位置与安全校验 1. 模型简介与部署准备 Z-Image-Turbo-辉夜巫女是基于Z-Image-Turbo模型的LoRA变体,专门针对生成日系动漫风格"辉夜巫女"角色图像进行了优化。该模型通过Xinferen…...
从零到一:在Simulink中构建SVPWM仿真模型的实践指南
1. 为什么选择Simulink搭建SVPWM模型? 第一次接触电机控制时,我被各种专业术语搞得晕头转向。直到发现Simulink这个可视化工具,才真正理解了SVPWM(空间矢量脉宽调制)的精髓。就像用乐高积木搭建城堡,Simuli…...
Llama-3.2V-11B-cot多场景:科研论文插图理解、工程图纸解析、UI截图分析
Llama-3.2V-11B-cot多场景应用:科研论文插图理解、工程图纸解析、UI截图分析 1. 模型概述 Llama-3.2V-11B-cot是一款基于LLaVA-CoT论文实现的视觉语言模型,具备强大的图像理解和系统性推理能力。该模型采用MllamaForConditionalGeneration架构…...
UG/NX Block UI Styler字符串控件避坑指南:常见问题与解决方案
UG/NX Block UI Styler字符串控件避坑指南:常见问题与解决方案 在UG/NX二次开发中,Block UI Styler作为可视化对话框设计工具,其字符串控件(String Control)是使用频率最高的交互元素之一。无论是参数输入、状态显示还…...
OpenClaw × 88API:不用注册 Anthropic,5 分钟让 AI Agent 接入 Claude 4.6(2026 完整教程)
折腾了两天,最后 5 分钟搞定 上周我想用 OpenClaw 搭一个能自动重构代码的 Agent。选定 Claude 4.6 当大脑——毕竟它在 Tool Use 精准度和长上下文推理上确实是第一梯队。 结果卡在了第一步:Anthropic 官方账号注册要海外手机号,好不容易注…...
从聊天机器人到业务执行者:Agentic Orchestration 如何重构 Java 后端体系
引言 在 RAG 1.0 时代,我们费尽心思让 AI“说得对、答得准”; 而进入 2026 年的 Agentic Orchestration(智能体编排) 时代,我们的目标已经变成:让 AI 做得对、跑得稳、能闭环。 用户说“帮我把昨天买贵的衣…...
实时手机检测-通用:5分钟快速部署,小白也能轻松上手
实时手机检测-通用:5分钟快速部署,小白也能轻松上手 1. 模型简介 实时手机检测-通用是一款基于DAMOYOLO-S框架的高性能目标检测模型,专门用于在各种场景中快速准确地检测手机设备。这个模型在精度和速度上都超越了传统的YOLO系列方法&#…...
