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

代码随想录训练营

Day45代码随想录

322.零钱兑换

1.题目描述

给你一个整数数组 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 <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

2.解题思路及代码实现

本题注意是最少的组合数,那么dp[j]就代表总额为j所能代表的最少组合数量,如果dp[j-coins[i]]存在那么递推公式为dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for (int i = 0; i <= amount; i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {if (dp[j-coins[i]]!=Integer.MAX_VALUE)dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}return dp[amount]==Integer.MAX_VALUE ? -1:dp[amount];}
}

279.完全平方数

1.题目描述

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

  • 1 <= n <= 104

2.解题思路及代码实现

其实本题和零钱兑换思路一样,

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];for (int i = 0; i <=n ; i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int i = 1; i <= (int)Math.sqrt(n); i++) {int amount = i*i;for (int j = amount; j <=n ; j++) {if (dp[j-amount]!= Integer.MAX_VALUE)dp[j] = Math.min(dp[j],dp[j-amount]+1);}}return dp[n];}
}

相关文章:

代码随想录训练营

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

java中的变量、数据类型、人机交互

变量 变量要素 1、类型&#xff1b;每一个变量都需要定义类型&#xff08;强类型&#xff09;其它语言有弱类型&#xff08;js&#xff09; 2、变量名&#xff1b; 3、存储的值&#xff1b; 声明方式&#xff1a; 数据类型 变量名 变量值&#xff1b; public static vo…...

Python中的生成器是什么

生成器的工作原理 只要Python函数的主体中有yield关键字,该函数就是生成器函数。调用生成器函数,返回一个生成器对象。也就是说,生成器函数是生成器工厂。 下面以一个简单的函数说明生成器的行为: def gen123():yield 1yield 2yield 3print(gen123) # <function gen…...

【Camera2完整流程分析四】从log角度分析CameraService启动流程

下面直接带你通过log打印来一起读CameraService启动的过程。 1)Camera service对象构建,在启动的时候先创建CameraService 这里会打印: CameraService: CameraService started (pid=559)接着启动的时候会执行 –》onFirstRef() 进入这里面看,先输出打印: CameraService:…...

基于SSM SpringBoot vue教务排课系统

基于SSM SpringBoot vue教务排课系统 系统功能 登录 个人中心 学生信息管理 教师信息管理 课室信息管理 班级信息管理 系别信息管理 专业信息管理 课程信息管理 选课信息管理 课表信息管理 开发环境和技术 开发语言&#xff1a;Java 使用框架: SSM(Spring SpringMVC Myba…...

深入理解 LinkedList 及底层源码分析

LinkedList 是基于链表结构的一种 List&#xff0c;在分析 LinkedList 源码前我们先对对链表结构做一个简单的了解。 一、链表的概念 链表是由一系列非连续的节点组成的存储结构&#xff0c;简单分下类的话&#xff0c;链表又分为_单向链表和双向链表&#xff0c;而单向 / 双…...

美易官方:英伟达业绩将难以撑起股价?

美股市场似乎总是对各大公司的业绩表现抱有极大的期待&#xff0c;就像一个永远填不饱的“巨胃”。在这样的市场环境下&#xff0c;即使是业绩骄人的公司也可能难以支撑其股价。英伟达&#xff0c;这家在图形处理单元&#xff08;GPU&#xff09;领域享有盛誉的公司&#xff0c…...

超实用干货!FP独立站引流攻略

在当前的市场环境下&#xff0c;对于希望继续从事FP和黑五类产品销售的商家来说&#xff0c;搭建独立站绝对是一个明智的选择。没有了第三方平台的限制&#xff0c;拥有自己的独立站意味着你可以完全掌控自己的商业策略和操作。 但脱离了平台&#xff0c;独立站推广会更加困难。…...

php之框架底层中间件模式开发实现、array_reduce的应用

众所周知php框架的中间件核心是通过array_reduce实现的 php之框架中间件模式开发实现、array_reduce的应用 1.先写个测试用例看一下函数的特性2.根据执行特性实现中间件 1.先写个测试用例看一下函数的特性 <?phpfunction kernal($a,$b){return $a . " and " .…...

fabric搭建生产网络

fabric搭建生产网络 一、生成组织结构与身份证书 解包 hyperledger-fabric-linux-amd64-2.5.0.tar.gz 1.1、crypto-config.yaml配置文件 ./bin/cryptogen showtemplate > crypto-config.yaml 将crypto-config.yaml内容修改为&#xff1a; # -------------------------…...

聊聊 ASP.NET Core 中间件(二):中间件和筛选器的区别

前言 有些小伙伴看到上一篇文章后&#xff0c;可能会发现中间件和我们之前讲的筛选器非常类似&#xff0c;比如它们都是通过 next 串起来的一系列的组件&#xff0c;并且都可以在请求处理前后执行代码&#xff0c;都可以通过不执行 next 来进行请求的终止。那么筛选器和中间件…...

Nginx配置Https缺少SSL模块

1、Linux下Nginx配置https nginx下载和安装此处就忽略&#xff0c;可自行百度 1.1、配置https 打开nginx配置文件 vim /opt/app/nginx/conf/nginx.conf相关https配置 server {listen 443 ssl; #开放端口server_name echarts.net;#域名#redirect to https#ssl on; #旧版#ssl证…...

超详细——集成学习——Adaboost实现多分类——附代码

资料参考 1.【集成学习】boosting与bagging_哔哩哔哩_bilibili 集成学习——boosting与bagging 强学习器&#xff1a;效果好&#xff0c;模型复杂 弱学习器&#xff1a;效果不是很好&#xff0c;模型简单 优点 集成学习通过将多个学习器进行结合&#xff0c;常可获得比单一…...

串口通信标准RS232 RS485 RS422的区别

很多工程师经常把RS-232、RS-422、RS-485称为通讯协议&#xff0c;其实这是不对的&#xff0c;它们仅仅是关于串口通讯的一个机械和电气接口标准&#xff08;顶多是网络协议中的物理层&#xff09;&#xff0c;不是通讯协议&#xff0c;那它们又有哪些区别呢&#xff1a; 第一…...

jdk环境安装

jdk安装 创建软件安装的目录 mkdir -p /bigdata/{soft,server} /bigdata/soft 安装文件的存放目录 /bigdata/server 软件安装的目录 把安装的软件上传到/bigdata/soft 目录 解压到指定目录 -C :指定解压到指定目录 tar -zxvf /bigdata/soft/jdk-8u241-linux-x64.tar.gz -C /b…...

QT+网络调试助手+TCP服务器

一、UI界面设计 二、单线程 代码设计 1、 查找合法的本地地址&#xff0c;用于当作服务器的IP地址 #include <QThread> #include <QTcpSocket> #include <QNetworkInterface> #include <QMessageBox>QList<QHostAddress> ipAddressesList QNe…...

【unity】(1)场景

Unity的场景&#xff08;Scene&#xff09;是构建游戏中各种环境和级别的基础。一个场景可以包含游戏中的所有对象&#xff0c;如角色、道具、地形等。 创建和管理场景 创建新场景&#xff1a; 在Unity编辑器中&#xff0c;选择File > New Scene&#xff0c;或者使用快捷键…...

【Linux】进程间通信IPC机制

目录 一、无名管道 二、有名管道 三、共享内存 四、信号量 五、消息队列 六、套接字 一、无名管道 1.只能用于具有亲缘关系的进程之间的通信(也就是父子进程或者兄弟进程)。 2.是一个单工的通信模式&#xff0c;具有固定的读端和写端。 3.管道也可以看成是一种特殊的文件…...

【如此简单!数据库入门系列】之效率基石 -- 磁盘空间管理

文章目录 1 前言2 磁盘空间管理3 磁盘空间管理的实现4 存储对象关系5 总结6 系列文章 1 前言 如何将表中的记录存储在物理磁盘上呢&#xff1f; 概念模式中&#xff0c;记录&#xff08;Record&#xff09;表示表中的一行数据&#xff0c;由多个列&#xff08;字段或者属性&…...

专业渗透测试 Phpsploit-Framework(PSF)框架软件小白入门教程(五)

本系列课程&#xff0c;将重点讲解Phpsploit-Framework框架软件的基础使用&#xff01; 本文章仅提供学习&#xff0c;切勿将其用于不法手段&#xff01; 继续接上一篇文章内容&#xff0c;讲述如何进行Phpsploit-Framework软件的基础使用和二次开发。 在下面的图片中&#…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

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

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

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...