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

【测试岗】手撕代码 - 零钱兑换

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,记录凑成每个金额所需的最少硬币数,从而自底向上地解决问题。

具体步骤如下

  1. 初始化动态规划数组 dp
  • dp[i] 表示凑成金额 i 所需的最少硬币数。首先我们将所有金额的值初始化为一个较大的数(如无穷大),表示暂时无法凑成这个金额。
  • 特别地,dp[0] = 0,因为凑成金额 0 所需的硬币数是 0。
  1. 遍历所有的金额 i
  • 对于每个金额 i,我们尝试每一种硬币面额 coin,如果当前硬币面额小于等于 i,则通过状态转移方程更新 dp[i] 的值。
  • 状态转移方程为:dp[i] = min(dp[i], dp[i - coin] + 1),其中 dp[i - coin] 表示减去一个当前硬币后剩余金额的最优解。
  1. 结果判断
  • 当遍历完所有金额后,检查 dp[amount] 的值。如果它仍然是无穷大,表示无法凑成该金额,返回 -1;否则,返回 dp[amount],即凑成 amount 所需的最少硬币数。
3. 算法分析

时间复杂度

  • 内层循环遍历 coins,外层循环遍历 amount,因此时间复杂度为 O(amount * n),其中 n 是硬币的种类数。

空间复杂度

  • 由于我们使用了一个大小为 amount + 1 的数组来存储每个金额的最少硬币数,因此空间复杂度为 O(amount)。

相关文章:

【测试岗】手撕代码 - 零钱兑换

322. 零钱兑换 题目描述 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。 你可以认为每种…...

菱形继承的类对父类的初始化、组合、多态、多态的原理等的介绍

文章目录 前言一、菱形继承的类对父类的初始化二、组合三、 多态1. 构成多态2. 虚函数3. 虚函数的重写4. 虚函数重写的两个例外1. 协变2. 析构函数的重写 5. C11 final 和 override1. final2. override 6. 设计不想被继承的类7. 重载、覆盖&#xff08;重写&#xff09;、 隐藏…...

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详解及简单配置

&#x1f680;个人主页&#xff1a;小羊 &#x1f680;所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 前言一、包管理器1.1 apt1.2 yum 二、Linux编辑器——vim2.1 vim的三种模式2.2 vim普通模式常用命令2.2.1 移动…...

AVL树实现

1.AVL的概念 1.AVL树属于二叉搜索树的一种&#xff0c;但它不同与普通的二叉搜索树还具有以下的性质&#xff1a; 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的&#xff0c;所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概…...

初始MYSQL数据库(6)—— 事务

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; MYSQL 目录 事务的概念 事务的ACID特性 使用事务 查看支持事务的存储引擎 事务的语法 保存点 自动/手动提交事务 事务的隔离性和…...

0基础学习PyTorch——GPU上训练和推理

大纲 创建设备训练推理总结 在《Windows Subsystem for Linux——支持cuda能力》一文中&#xff0c;我们让开发环境支持cuda能力。现在我们要基于《0基础学习PyTorch——时尚分类&#xff08;Fashion MNIST&#xff09;训练和推理》&#xff0c;将代码修改成支持cuda的训练和推…...

这款免费工具让你的电脑焕然一新,专业人士都在用

HiBit Uninstaller 采用单一可执行文件的形式,无需复杂的安装过程,用户可以即刻开始使用。这种便捷性使其成为临时使用或紧急情况下的理想选择。尽管体积小巧,但其功能却异常强大,几乎不会对系统性能造成任何负面影响。 这款工具的一大亮点是其多样化的功能。它不仅能够常规卸…...

Java高级Day52-BasicDAO

138.BasicDao 基本说明&#xff1a; DAO&#xff1a;data access object 数据访问对象 这样的通用类&#xff0c;称为 BasicDao&#xff0c;是专门和数据库交互的&#xff0c;即完成对数据库(表)的crud操作 在BasicDao 基础上&#xff0c;实现一张表对应一个Dao&#xff0c;…...

【OceanBase 诊断调优】—— SQL 诊断宝典

视频 OceanBase 数据库 SQL 诊断和优化&#xff1a;https://www.oceanbase.com/video/5900015OB Cloud 云数据库 SQL 诊断与调优的应用实践&#xff1a;https://www.oceanbase.com/video/9000971SQL 优化&#xff1a;https://www.oceanbase.com/video/9000889阅读和管理SQL执行…...

微服务Redis解析部署使用全流程

目录 1、什么是Redis 2、Redis的作用 3、Redis常用的五种基本类型&#xff08;重要知识点&#xff09; 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) // 按值查找元素&#xff0c;找到返回指定位置迭代器&#xff0c;找不到返回结束迭代器位置 // 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

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 专栏介绍 在软件开发和日常使用中&#xff0c;BUG是不可避免的。本专栏致力于为广大开发者和技术爱好者提供一个关于BUG解决的经…...

matlab入门学习(四)多项式、符号函数、数据统计

一、多项式 %多项式&#xff08;polynomial&#xff09;%创建 p[1,2,3,4] %系数向量&#xff0c;按x降幂排列&#xff0c;最右边是常数&#xff08;x的0次幂&#xff09; f1poly2str(p,x) %系数向量->好看的字符串 f x^3 2 x^2 3 x 4&#xff08;不能运算的式子&#xf…...

leetcode621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表&#xff0c;用字母 A 到 Z 表示&#xff0c;以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成&#xff0c;但有一个限制&#xff1a;两个 相同种类 的任务之间必须有长度为 n 的冷却时…...

Spark 的 Skew Join 详解

Skew Join 是 Spark 中为了解决数据倾斜问题而设计的一种优化机制。数据倾斜是指在分布式计算中&#xff0c;由于某些 key 具有大量数据&#xff0c;而其他 key 数据较少&#xff0c;导致某些分区的数据量特别大&#xff0c;造成计算负载不均衡。数据倾斜会导致个别节点出现性能…...

讯飞星火编排创建智能体学习(一)最简单的智能体构建

目录 开篇 智能体的概念 编排创建智能体 创建第一个智能体 ​编辑 大模型节点 测试与调试 开篇 前段时间在华为全联接大会上看到讯飞星火企业级智能体平台的演示&#xff0c;对于拖放的可视化设计非常喜欢&#xff0c;刚开始以为是企业用户才有的&#xff0c;回来之后查…...

mac-m1安装nvm,docker,miniconda

1.安装minicondaMAC OS(M1)安装配置miniconda_mac-mini m1 conda-CSDN博客 2.安装nvm&#xff08;用第二个方法&#xff09;Mac电脑安装nvm(node包版本管理工具)-CSDN博客 3.安装docker dmg下载链接docker-toolbox-mac-docker-for-mac安装包下载_开源镜像站-阿里云 教程MacOS系…...

STM32F407之Flash

寄存器分类 一般寄存器分为只读存储器 (ROM) 随机存储器(RAM) 只读存储器 只读存储器也被称为ROM 在正常工作时只能读不能写。 只读存储器经历的阶段 ROM->PROM->EPROM->EEPROM ->Flash 优点&#xff1a;掉电不丢失&#xff0c;解构简单 缺点&#xff1a;只适…...

FastAPI安全防线:OAuth2 + JWT 实现无状态认证的完整流程

更多内容请见: 《Python Web项目集锦》 - 专栏介绍和目录 在现代Web应用开发中,安全认证是构建可靠API的基石。FastAPI通过其强大的安全组件,为开发者提供了实现安全、可扩展认证系统的工具。本文将深入剖析OAuth2与JWT在FastAPI中的整合实现,揭示无状态认证的完整流程,提…...

LiuJuan20260223Zimage新手必看:从CSDN博客文档到本地成功出图的避坑指南

LiuJuan20260223Zimage新手必看&#xff1a;从CSDN博客文档到本地成功出图的避坑指南 你是不是也遇到过这种情况&#xff1f;在CSDN上看到一个有趣的AI绘画模型&#xff0c;比如这个LiuJuan20260223Zimage&#xff0c;文档写得清清楚楚&#xff0c;但自己一上手部署&#xff0…...

Python 入门后进阶:用 Pixel Mind Decoder 完成你的第一个 AI 项目

Python 入门后进阶&#xff1a;用 Pixel Mind Decoder 完成你的第一个 AI 项目 1. 从零开始你的AI项目之旅 刚学完Python基础语法&#xff0c;是不是觉得光写些练习题和小脚本不够过瘾&#xff1f;今天我们就来做个有意思的实战项目——用AI分析文本情绪&#xff0c;再给它套…...

MQTT安全连接不止一种:用MQTTnet库玩转C#客户端单向与双向认证

MQTT安全连接实战&#xff1a;从单向认证到双向认证的C#实现精要 物联网设备间的数据传输安全一直是开发者关注的核心问题。MQTT协议作为轻量级的消息传输协议&#xff0c;在工业自动化、智能家居等领域广泛应用&#xff0c;但其默认的1883端口通信并不加密。本文将深入探讨如何…...

Emu3.5 视觉 tokenizer 及其 decoder 的训练过程

下面我把 Emu3.5 视觉 tokenizer 及其 decoder 的训练完整过程,按照“论文明确写到的部分”“公开代码能对上的部分”“需要用开源近似路线复现的部分”三层重新整理。先给结论: 结论:Emu3.5 的视觉部分其实不是“一次性训练完一个模块”,而是至少分成两条链路: 第一条是…...

SEO_掌握这几个核心技巧让你的SEO事半功倍

<h2>SEO核心技巧&#xff1a;让你的网站事半功倍的秘诀</h2> <p>在当今数字化时代&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;已经成为了网站运营者提升网站流量和品牌知名度的关键。SEO 的复杂性常常让新手感到困惑&#xff0c;不知道从哪里入手。…...

如何一键获取国家中小学智慧教育平台所有电子课本?这个智能下载工具给你答案

如何一键获取国家中小学智慧教育平台所有电子课本&#xff1f;这个智能下载工具给你答案 【免费下载链接】tchMaterial-parser 国家中小学智慧教育平台 电子课本下载工具 项目地址: https://gitcode.com/GitHub_Trending/tc/tchMaterial-parser 还在为繁琐的教材下载流程…...

BlueDot BME280库深度解析:嵌入式多传感器驱动实践

1. BlueDot BME280 库技术解析&#xff1a;面向嵌入式工程师的多传感器驱动实践指南BME280 是博世&#xff08;Bosch&#xff09;推出的高精度环境传感器&#xff0c;集成温度、相对湿度与气压三参数测量能力&#xff0c;广泛应用于气象站、IoT终端、无人机姿态补偿及室内环境监…...

C语言回调函数原理与实战应用指南

C语言回调函数深度解析与实践应用1. 函数指针基础1.1 函数指针概念函数指针是指向函数的指针变量&#xff0c;与普通指针变量不同&#xff0c;它指向的是代码区而非数据区。标准定义形式为&#xff1a;返回值类型 (*指针变量名)(参数类型列表);关键特征&#xff1a;指针变量名必…...

【Android FWK】VR一体机全局菜单实战:从VirtualDisplay原理到系统级交互(上)

文章目录 一、从弹窗穿透到VR全局菜单 二、VirtualDisplay在VR中的适配原理 2.1 VR显示系统的特殊性 2.2 VR适配的核心代码 三、VR全局菜单的完整实现 3.1 系统架构设计 3.2 菜单呼出机制:手势+语音双重触发 3.3 菜单界面:适配VR的3D布局 3.4 系统交互:调节系统设置 四、VR环…...