第十课 贪心
文章目录
- 第十课 贪心
- lc 322.零钱兑换--中等
- 题目描述
- 代码展示
- lc860.柠檬水找零--简单
- 题目描述
- 代码展示
- lc455.分发饼干--简单
- 题目描述
- 代码展示
- lc122.买卖股票的最佳时机II--中等
- 题目描述
- 代码展示
- lc45.跳跃游戏II--中等
- 题目描述
- 代码展示
- lc1665.完成所有任务的最少初始能量--困难
- 题目描述
- 代码展示
第十课 贪心
lc 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 <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
代码展示
class Solution {public int coinChange(int[] coins, int amount) {int INF = (int)1e9; // 定义一个无穷大的值,用于初始化 dp 数组int[] opt = new int[amount + 1]; // 创建一个 dp 数组,用于存储凑成各个金额所需的最小硬币数量opt[0] = 0; // 初始化金额为 0 时的硬币数量为 0// 从金额 1 开始逐步计算到 amountfor (int i = 1; i <= amount; i++) {opt[i] = INF; // 初始化为无穷大,表示无法凑成该金额for (int j = 0; j < coins.length; j++) {if (i - coins[j] >= 0) {// 尝试使用每个硬币来凑成金额 i,并更新 dp[i] 的最小值opt[i] = Math.min(opt[i], opt[i - coins[j]] + 1);}}}// 如果 opt[amount] 仍然等于 INF,表示无法凑成总金额,返回 -1;否则返回 opt[amount]if (opt[amount] >= INF) {opt[amount] = -1;}return opt[amount];}
}
lc860.柠檬水找零–简单
题目描述
在柠檬水摊上,每一杯柠檬水的售价为 5
美元。顾客排队购买你的产品,(按账单 bills
支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5
美元、10
美元或 20
美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5
美元。
注意,一开始你手头没有任何零钱。
给你一个整数数组 bills
,其中 bills[i]
是第 i
位顾客付的账。如果你能给每位顾客正确找零,返回 true
,否则返回 false
。
示例 1:
输入:bills = [5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。
示例 2:
输入:bills = [5,5,10,10,20]
输出:false
解释:
前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零,所以答案是 false。
提示:
1 <= bills.length <= 105
bills[i]
不是5
就是10
或是20
代码展示
class Solution {public boolean lemonadeChange(int[] bills) {int fiveCount = 0;int tenCount = 0;for (int bill : bills) {if (bill == 5) {fiveCount++;} else if (bill == 10) {if (fiveCount > 0) {fiveCount--;tenCount++;} else {return false;}} else { // 当账单为20美元时if (tenCount > 0 && fiveCount > 0) {tenCount--;fiveCount--;} else if (fiveCount >= 3) {fiveCount -= 3;} else {return false;}}}return true;}
}
lc455.分发饼干–简单
题目描述
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i
,都有一个胃口值 g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j
,都有一个尺寸 s[j]
。如果 s[j] >= g[i]
,我们可以将这个饼干 j
分配给孩子 i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
代码展示
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;int satisfied = 0;while (i < g.size() && j < s.size()) {if (s[j] >= g[i]) {satisfied++;i++;}j++;}return satisfied;}
};
lc122.买卖股票的最佳时机II–中等
题目描述
给你一个整数数组 prices
,其中 prices[i]
表示某支股票第 i
天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。
示例 2:
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。
示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
代码展示
class Solution {
public:int maxProfit(vector<int>& prices) { int ans = 0; // 初始化最大利润为0int n = prices.size(); // 获取股票价格数组的长度for (int i = 1; i < n; ++i) { // 遍历股票价格数组ans += max(0, prices[i] - prices[i - 1]); // 计算并累加利润,如果是负数则不累加}return ans; // 返回最大利润}
};
lc45.跳跃游戏II–中等
题目描述
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
- 题目保证可以到达
nums[n-1]
代码展示
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int jumps = 0;int farthest = 0;int currentEnd = 0;for (int i = 0; i < n - 1; i++) {farthest = max(farthest, i + nums[i]); // 更新当前能够跳到的最远位置if (i == currentEnd) { // 如果到达当前能够跳的最远位置jumps++; // 增加跳跃次数currentEnd = farthest; // 更新当前能够跳到的最远位置}}return jumps;}
};
lc1665.完成所有任务的最少初始能量–困难
题目描述
给你一个任务数组 tasks
,其中 tasks[i] = [actuali, minimumi]
:
actuali
是完成第i
个任务 需要耗费 的实际能量。minimumi
是开始第i
个任务前需要达到的最低能量。
比方说,如果任务为 [10, 12]
且你当前的能量为 11
,那么你不能开始这个任务。如果你当前的能量为 13
,你可以完成这个任务,且完成它后剩余能量为 3
。
你可以按照 任意顺序 完成任务。
请你返回完成所有任务的 最少 初始能量。
示例 1:
输入:tasks = [[1,2],[2,4],[4,8]]
输出:8
解释:
一开始有 8 能量,我们按照如下顺序完成任务:- 完成第 3 个任务,剩余能量为 8 - 4 = 4 。- 完成第 2 个任务,剩余能量为 4 - 2 = 2 。- 完成第 1 个任务,剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余,但是如果一开始只有 7 能量是不能完成所有任务的,因为我们无法开始第 3 个任务。
示例 2:
输入:tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出:32
解释:
一开始有 32 能量,我们按照如下顺序完成任务:- 完成第 1 个任务,剩余能量为 32 - 1 = 31 。- 完成第 2 个任务,剩余能量为 31 - 2 = 29 。- 完成第 3 个任务,剩余能量为 29 - 10 = 19 。- 完成第 4 个任务,剩余能量为 19 - 10 = 9 。- 完成第 5 个任务,剩余能量为 9 - 8 = 1 。
示例 3:
输入:tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出:27
解释:
一开始有 27 能量,我们按照如下顺序完成任务:- 完成第 5 个任务,剩余能量为 27 - 5 = 22 。- 完成第 2 个任务,剩余能量为 22 - 2 = 20 。- 完成第 3 个任务,剩余能量为 20 - 3 = 17 。- 完成第 1 个任务,剩余能量为 17 - 1 = 16 。- 完成第 4 个任务,剩余能量为 16 - 4 = 12 。- 完成第 6 个任务,剩余能量为 12 - 6 = 6 。
提示:
1 <= tasks.length <= 105
1 <= actuali <= minimumi <= 104
代码展示
class Solution {
public:int minimumEffort(vector<vector<int>>& tasks) {/*消耗(actual)小,门槛(minimum)大,是先做的条件按actual + (-minimum)排序*/sort(tasks.begin(), tasks.end(),[](vector<int>& a, vector<int>& b) {return a[0] - a[1] < b[0] - b[1];});// 正序做任务,但计算要倒序int energy = 0; // 任务全部做完(什么也不用再做了)的时候,还需要0的能量for (int i = tasks.size() - 1; i >= 0; i--) {// minimum energy + actualenergy = max(tasks[i][1], energy + tasks[i][0]);}return energy;}
};
相关文章:

第十课 贪心
文章目录 第十课 贪心lc 322.零钱兑换--中等题目描述代码展示 lc860.柠檬水找零--简单题目描述代码展示 lc455.分发饼干--简单题目描述代码展示 lc122.买卖股票的最佳时机II--中等题目描述代码展示 lc45.跳跃游戏II--中等题目描述代码展示 lc1665.完成所有任务的最少初始能量--…...

5分钟理解什么是卷积的特征提取
大家好啊,我是董董灿。 卷积算法之所以重要,关键在于其提取特征的能力。 5分钟入门卷积算法中提到,卷积模仿的就是人眼识图的过程,以“感受野”的视角去扫描图片,从而获取不同区域的图片信息。 在这一过程中&#x…...

Legion Y9000X IRH8 2023款(82Y3)原装出厂OEM预装Windows11系统
lenovo联想电脑笔记本拯救者原厂win11系统镜像 下载链接:https://pan.baidu.com/s/15G01j7ROVqOFOETccQSKHg?pwdt1ju 系统自带所有驱动、出厂主题壁纸、Office办公软件、联想电脑管家等预装程序 所需要工具:32G或以上的U盘 文件格式:ISO…...

【Acwing1010】拦截导弹(LIS+贪心)题解
题目描述 思路分析 本题有两问,第一问直接用lis的模板即可,下面重点看第二问 思路是贪心: 贪心流程: 从前往后扫描每一个数,对于每个数: 情况一:如果现有的子序列的结尾都小于当前的数&…...

DevicData-D-XXXXXXXX勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复
引言: 在数字时代,数据安全成为一项至关重要的挑战。DevicData-D-XXXXXXXX勒索病毒(以下简称DevicData病毒)是这场战斗中的新敌人,它能够以毁灭性的方式加密您的数据,迫使您在数据和时间之间做出艰难的选择…...

从入门到精通,30天带你学会C++【第七天:for循环和while循环以及数组的学习】(学不会你找我)
目录 Everyday English 前言 数组 数组的概念 数组的定义 数组的下标 for循环 循环是什么 基本格式 多重循环 while循环 do-while循环 总结 Everyday English To shine , not be illuminated. 去发光,而不是被照亮。 前言 好久不见,…...
Python 编程基础 | 第五章-类与对象 | 5.2、数据成员
一、数据成员 数据成员是指类中定义的变量,即属性,根据定义位置,又可以分为类属性和实例属性,下面分别进行介绍。 1、实例属性 实例属性是指定义在类的方法中的属性,该属性属于当前实例,例如:…...

PHP 个人愿望众筹网站系统mysql数据库web结构apache计算机软件工程网页wamp
一、源码特点 PHP 个人愿望众筹网站系统是一套完善的web设计系统,对理解php编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。 php 个人愿望众筹网站 代码 https://download.csdn.net/download/qq_41221322/8…...
JS--判断空值(null、undefined、NaN、false、空字符串等)
原文网址:JS--判断空值(null、undefined、NaN、false、空字符串等)_IT利刃出鞘的博客-CSDN博客 简介 本文介绍JavaScript判断空值的方法。 空值包括:undefined,null,NaN,,false,{}࿰…...

ChatGPT 背后包含了哪些技术?
ChatGPT 是由OpenAI开发的一款基于GPT-3(Generative Pre-trained Transformer 3)的人工智能语言模型。这个模型是使用多种编程语言和技术组合编写的。 首先,ChatGPT 使用了 Python 作为主要的编程语言。Python 是一种流行的高级编程语言&…...

Vue Router(二)
目录 一、嵌套路由 1、路由定义 2、代码例子 3、重定向 二、懒加载 1、缘由 2、代码例子 三、导航守卫 1、全局前置守卫 2、全局后置守卫 3、meta元信息 四、生命周期 1、解释 2、执行顺序 3、例子 五、keep-alive组件缓存(保活) 1、介…...

ELK整合springboot(第二课)
一、创建一个springboot的项目 pom文件如下: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLo…...
运维常见的22个故障排查和10个问题解决技巧大汇总!
作为运维,多多少少会碰见这样那样的问题或故障,从中总结经验,查找问题,汇总并分析故障的原因,这是一个运维工程师良好的习惯。每一次技术的突破,都经历着苦闷,伴随着快乐,可我们还是…...

解决 TensorFlow 2.x 中的 “AttributeError: module ‘tensorflow‘ has no attribute ‘placeholder‘“ 错误
项目场景: 在使用 TensorFlow 框架实现深度学习应用时,可能会遇到以下错误: AttributeError: module tensorflow has no attribute placeholder问题描述 在 TensorFlow 1.x 版本中,placeholder 函数用于创建占位符张量。然而&a…...

新风机注意事项有哪些?
选择和使用新风机时,有几个关键注意事项需要牢记: 安装位置:新风机的安装位置很重要。通常情况下,应将其安装在室外以避免室内产生噪音和减少室内的体积占据。确保选择合适的安装位置,以便新风机能够顺利引入新鲜空气。…...

GitHub基础
1、仓库是什么意思?仓库拥有者是谁? 在软件开发或版本控制系统中,"仓库"(Repository)是指存储项目代码、配置文件、文档等相关文件的地方。它可以看作是一个中央存储库,用于管理和跟踪项目的各个…...
读书笔记--未来简史关键金句和阅读感悟
借着国庆假期,终于有时间研读了尤瓦尔.赫拉利的《未来简史》,作者的写作方式、文笔、观察视角都是我喜欢的类型,作者从古到今,谈到了上帝、神、宗教、科技、生物、智人到未来的超人智神(数据主义)ÿ…...

【Vue2.0源码学习】生命周期篇-销毁阶段(destroy)
文章目录 1. 前言2. 销毁阶段分析3. 总结 1. 前言 接下来到了生命周期流程的最后一个阶段——销毁阶段。从官方文档给出的生命周期流程图中可以看到,当调用了vm.$destroy方法,Vue实例就进入了销毁阶段,该阶段所做的主要工作是将当前的Vue实例…...
代理IP与Socks5代理在多领域的卓越应用
随着数字化时代的到来,网络工程师在跨界电商、爬虫、出海业务、网络安全和游戏等多个领域中扮演着至关重要的角色。在这些领域中,代理IP与Socks5代理技术已经成为网络工程师的得力助手,本文将深入探讨它们在技术世界中的卓越应用。 1. 跨界电…...
kafka怎么实现零拷贝(Zero-Copy)的?
Kafka 实现零拷贝(Zero-Copy)主要依赖于操作系统和底层网络库的支持,而不是特定的算法。这是因为零拷贝是一种优化数据传输的技术,通常是通过操作系统和硬件来实现的。以下是 Kafka 如何实现零拷贝的一般原理: 直接内存…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...