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

LeetCode hot100-85

https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-100-liked

322. 零钱兑换
已解答
中等
相关标签
相关企业
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量是无限的。

状态转移方程
dp[i] = min(dp[i], dp[i - coin] + 1)
这题没有用Integer.MAX_VALUE,用了amount+1来表示一个不可达的数,因为凑硬币就算是凑一块一块的也最多只需要amount个,amount+1就可以用来表示凑不出来的情况。
这题不用Integer.MAX_VALUE我看了下给的第二个案例就溢出了,coins =[2],amount =3。执行 dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
dp[2]=Math.min(Integer.MAX_VALUE,1)=1
dp[3]=Math.min(dp[3],dp[1]+1)。这里的dp[1]就是Integer.MAX_VALUE,加一直接溢出变成一个负数。dp[3]就是一个很小的负数了。结果就错了。。。。但是上一题就是那个hot100-84完全平方那个题就用了Integer.MAX_VALUE不会溢出,中间应该是有一些数学道理的,我也没理解,不深究了。。。
也可以不用Integer.MAX_VALUE,用一个Integer.MAX_VALUE/2,测试案例正常情况下是到不了这么大的,我试了下能过。见下面的第二种代码

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

相关文章:

LeetCode hot100-85

https://leetcode.cn/problems/coin-change/?envTypestudy-plan-v2&envIdtop-100-liked 322. 零钱兑换 已解答 中等 相关标签 相关企业 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。计算并返回可以凑…...

linux 内核数据包处理中的一些坑和建议

1、获取IP头部 iph ip_hdr(skb); struct sk_buff { ...... sk_buff_data_t transport_header; /* Transport layer header */ sk_buff_data_t network_header; /* Network layer header */ sk_buff_data_t mac_header; /* Link layer header */ ...... } 1&#xff0…...

C++ 的衰退复制(decay-copy)

目录 1.什么是衰退复制&#xff08;decay-copy&#xff09; 1.1.推导规则 1.2.LWG issue 929 1.3.想象中的 decay_copy 2.decay-copy 与 auto 2.1.为什么引入衰退复制 2.2. 成为 C 23 的语言特性 3.应用场景 4.总结 1.什么是衰退复制&#xff08;decay-copy&#xff0…...

vue-cli 5接入模块联邦 module federation

vue-cli 5接入模块联邦 module federation 模块联邦概念实现思路配置遇到的问题: 模块联邦概念 模块联邦由webpack 5最先推出的,让应用加载远程的代码模块来实现不同的Web应用共享代码片段.模块联邦分为两个角色,一个是生产者,一个是消费者.生产者暴露代码供消费者消费 (用一个…...

【Rust自学】3.6. 控制流:循环

3.6.0. 写在正文之前 欢迎来到Rust自学的第三章&#xff0c;一共有6个小节&#xff0c;分别是: 变量与可变性数据类型&#xff1a;标量类型数据类型&#xff1a;复合类型函数和注释控制流&#xff1a;if else控制流&#xff1a;循环&#xff08;本文&#xff09; 通过第二章…...

【第八节】git与github

目录 前言 一、 远程仓库概述 二、 创建、配置、连接推送远程仓库 2.1 在 GitHub 上创建仓库 2.2 生成 SSH Key 2.3 验证 SSH 连接 2.4 本地初始化仓库 2.5 推送本地仓库到远程 三、 管理远程仓库 3.1 查看远程仓库 3.2 提取远程仓库更新 3.3 推送更新到远程仓库 …...

win如何访问Linux数据库(本地)

对于数据库的学习&#xff0c;我们都是在localhost主机上进行操作&#xff0c;当我们在Linux系统上安装数据库时&#xff0c;我们就有了尝试在win上去访问Linux上的数据库的想法。 数据库中的用户&#xff1a; 我们都知道数据库中顶级的用户为root&#xff0c;在做创建用户的联…...

Windows设置所有软件默认以管理员身份运行

方法一、修改注册表 winr打开运行&#xff0c;输入“regedit”打开注册表&#xff1b; 打开此路径“计算机HKEY_LOCAL_MACHINESOFTWAREMicrosoftWindowsCurrentVersionPoliciesSystem”&#xff1b; 在右侧找到“EnableLUA”&#xff0c;将其值改为0&#xff0c;重启电脑。 …...

前端 计算发布时间(如“1小时前”、“3天前”等)

这样效果&#xff0c;在c端比较常见&#xff0c;通过前端也可以处理 代码如下&#xff1a; // 计算 小时timeAgo(createTime) {// 将 createTime 字符串转换为 Date 对象 const createDate new Date(createTime);const now new Date();const diffInSeconds Math.floor((now…...

shardingjdbc 4.0.0 seata分布式事务Failed to fetch schema问题

报错 12-18 15:18:35.931 [ERROR] [i.s.r.d.s.s.cache.AbstractTableMetaCache:63 ] [traceId:][spanId:] - get table meta of the table wh_stock_log error: Failed to fetch schema of xxx java.sql.SQLException: Failed to fetch schema of wh_stock_logat io.seata.r…...

罗德与施瓦茨NRT2功率反射仪,NRT2通过式功率计

罗德与施瓦茨NRT2功率反射仪NRT2 通过式功率计 描述 定向/通过式功率传感器在线测量正向和反向功率。在安装、维修和监控发射机、天线和射频发生器时&#xff0c;需要进行这些测量。R&SNRT系列由R&SNRT2功率反射计及各种R&SNRT Zxx定向功率传感器。 由于其测量功…...

QLineEdit限制输入固定字节数(UTF-8编码)

setMaxLength(int)只能用来限制输入的字符个数 QLineEdit *editor new QLineEdit(parent); editor->setMaxLength(32); 1、如果是单字节字符&#xff0c;如数字&#xff0c;字母等&#xff0c;字符数正好等于字节数 2、如果是多字节字符&#xff0c;UTF8编码时&#xff0…...

基于ubuntu的mysql 8.0安装教程

文章目录 1.查看版本2.切换到root账户3.下载安装包4.问题的解决5.查看是否解压成功6.安装我们的发布包7.更新包的内容8.下载mysql9.查看mysql的状态10.设置开机自启动11.登录mysql 公司里面的mysql根本不会出现在windows操作系统上面&#xff0c;下面我们演示的就是如何在ubunt…...

K8s ConfigMap的基础功能介绍

在 Kubernetes 中&#xff0c;ConfigMap 是一种用于管理配置信息的资源对象&#xff0c;它允许你将 配置信息与代码解耦&#xff0c;方便管理和更新应用配置&#xff0c;而无需重新构建镜像或重启服务。 ConfigMap 的功能 存储配置信息&#xff1a; 可以以 键值对 的形式存储配…...

Linux——Shell

if 语句 格式&#xff1a;if list; then list; [ elif list; then list; ] ... [ else list; ] fi 单分支 if 条件表达式; then 命令 fi 示例&#xff1a; #!/bin/bash N10 if [ $N -gt 5 ]; then echo yes fi # bash test.sh yes 双分支 if 条件表达式; then 命令 else 命令…...

armsom产品编译烧录Linux固件

1、开发环境及工具准备 Rockchip Linux 软件包&#xff1a;linux-5.10-gen-rkr4 主机&#xff1a; 安装VMware搭建虚拟机&#xff0c;版本为Ubuntu 20.04 (硬盘容量大于100G&#xff09; 安装远程连接工具MobaXterm&#xff08;可连接虚拟机方便文件传输&#xff09; 2、S…...

VSCode:Markdown插件安装使用 -- 最简洁的VSCode中Markdown插件安装使用

VSCode&#xff1a;Markdown插件安装使用 1.安装Marktext2.使用Marktext 本文&#xff0c;将在Visual Studio Code中&#xff0c;安装和使用Markdown插件&#xff0c;以Marktext插件为例。 1.安装Marktext 打开VSCode&#xff0c;侧边栏中找到扩展模块(或CtrlShiftX快捷键)&am…...

AI 行业发展趋势:科技创新引领未来变革

在当今数字化时代,人工智能(AI)行业正以前所未有的速度蓬勃发展,深刻地改变着我们的生活、工作和社会格局。从基础技术的突破到广泛的应用场景拓展,AI 展现出了一系列令人瞩目的发展趋势,预示着一个充满无限可能的未来。 一、技术创新持续突破 模型规模与性能提升 AI 模…...

FB爆款打法实操经验总结

在进行Facebook广告投放时&#xff0c;有效的预算控制、素材测试、广告效果评估和lookalike受众的管理是至关重要的。通过科学的方法和策略&#xff0c;您可以在竞争激烈的市场中实现更好的业绩。 01 预算控制 测试阶段的广告不稳定性&#xff1a;在投放广告的初期&#xff0c…...

微信小程序TTS解决方案

微信小程序原生语音合成 API&#xff08;基础且简单&#xff09; 介绍&#xff1a;微信小程序提供了基础的语音合成能力。通过wx.createInnerAudioContext()等相关API&#xff0c;可以实现简单的语音播放功能。不过它主要是用于音频播放&#xff0c;对于完整的文本到语音&#…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

2.3 物理层设备

在这个视频中&#xff0c;我们要学习工作在物理层的两种网络设备&#xff0c;分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间&#xff0c;需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质&#xff0c;假设A节点要给…...

DeepSeek越强,Kimi越慌?

被DeepSeek吊打的Kimi&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...