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

第十课 贪心

文章目录

  • 第十课 贪心
    • 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; // 返回最大利润}
};

image-20231007173225396

lc45.跳跃游戏II–中等

题目描述

给定一个长度为 n0 索引整数数组 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;}
};

image-20231007173359581

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;}
};

image-20231007173715906

image-20231007173724698

相关文章:

第十课 贪心

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

5分钟理解什么是卷积的特征提取

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

Legion Y9000X IRH8 2023款(82Y3)原装出厂OEM预装Windows11系统

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

【Acwing1010】拦截导弹(LIS+贪心)题解

题目描述 思路分析 本题有两问&#xff0c;第一问直接用lis的模板即可&#xff0c;下面重点看第二问 思路是贪心&#xff1a; 贪心流程&#xff1a; 从前往后扫描每一个数&#xff0c;对于每个数&#xff1a; 情况一&#xff1a;如果现有的子序列的结尾都小于当前的数&…...

DevicData-D-XXXXXXXX勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复

引言&#xff1a; 在数字时代&#xff0c;数据安全成为一项至关重要的挑战。DevicData-D-XXXXXXXX勒索病毒&#xff08;以下简称DevicData病毒&#xff09;是这场战斗中的新敌人&#xff0c;它能够以毁灭性的方式加密您的数据&#xff0c;迫使您在数据和时间之间做出艰难的选择…...

从入门到精通,30天带你学会C++【第七天:for循环和while循环以及数组的学习】(学不会你找我)

目录 Everyday English 前言 数组 数组的概念 数组的定义 数组的下标 for循环 循环是什么 基本格式 多重循环 while循环 do-while循环 总结 Everyday English To shine , not be illuminated. 去发光&#xff0c;而不是被照亮。 前言 好久不见&#xff0c…...

Python 编程基础 | 第五章-类与对象 | 5.2、数据成员

一、数据成员 数据成员是指类中定义的变量&#xff0c;即属性&#xff0c;根据定义位置&#xff0c;又可以分为类属性和实例属性&#xff0c;下面分别进行介绍。 1、实例属性 实例属性是指定义在类的方法中的属性&#xff0c;该属性属于当前实例&#xff0c;例如&#xff1a;…...

PHP 个人愿望众筹网站系统mysql数据库web结构apache计算机软件工程网页wamp

一、源码特点 PHP 个人愿望众筹网站系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 php 个人愿望众筹网站 代码 https://download.csdn.net/download/qq_41221322/8…...

JS--判断空值(null、undefined、NaN、false、空字符串等)

原文网址&#xff1a;JS--判断空值(null、undefined、NaN、false、空字符串等)_IT利刃出鞘的博客-CSDN博客 简介 本文介绍JavaScript判断空值的方法。 空值包括&#xff1a;undefined&#xff0c;null&#xff0c;NaN&#xff0c;&#xff0c;false&#xff0c;{}&#xff0…...

ChatGPT 背后包含了哪些技术?

ChatGPT 是由OpenAI开发的一款基于GPT-3&#xff08;Generative Pre-trained Transformer 3&#xff09;的人工智能语言模型。这个模型是使用多种编程语言和技术组合编写的。 首先&#xff0c;ChatGPT 使用了 Python 作为主要的编程语言。Python 是一种流行的高级编程语言&…...

Vue Router(二)

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

ELK整合springboot(第二课)

一、创建一个springboot的项目 pom文件如下&#xff1a; <?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个问题解决技巧大汇总!

作为运维&#xff0c;多多少少会碰见这样那样的问题或故障&#xff0c;从中总结经验&#xff0c;查找问题&#xff0c;汇总并分析故障的原因&#xff0c;这是一个运维工程师良好的习惯。每一次技术的突破&#xff0c;都经历着苦闷&#xff0c;伴随着快乐&#xff0c;可我们还是…...

解决 TensorFlow 2.x 中的 “AttributeError: module ‘tensorflow‘ has no attribute ‘placeholder‘“ 错误

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

新风机注意事项有哪些?

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

GitHub基础

1、仓库是什么意思&#xff1f;仓库拥有者是谁&#xff1f; 在软件开发或版本控制系统中&#xff0c;"仓库"&#xff08;Repository&#xff09;是指存储项目代码、配置文件、文档等相关文件的地方。它可以看作是一个中央存储库&#xff0c;用于管理和跟踪项目的各个…...

读书笔记--未来简史关键金句和阅读感悟

借着国庆假期&#xff0c;终于有时间研读了尤瓦尔.赫拉利的《未来简史》&#xff0c;作者的写作方式、文笔、观察视角都是我喜欢的类型&#xff0c;作者从古到今&#xff0c;谈到了上帝、神、宗教、科技、生物、智人到未来的超人智神&#xff08;数据主义&#xff09;&#xff…...

【Vue2.0源码学习】生命周期篇-销毁阶段(destroy)

文章目录 1. 前言2. 销毁阶段分析3. 总结 1. 前言 接下来到了生命周期流程的最后一个阶段——销毁阶段。从官方文档给出的生命周期流程图中可以看到&#xff0c;当调用了vm.$destroy方法&#xff0c;Vue实例就进入了销毁阶段&#xff0c;该阶段所做的主要工作是将当前的Vue实例…...

代理IP与Socks5代理在多领域的卓越应用

随着数字化时代的到来&#xff0c;网络工程师在跨界电商、爬虫、出海业务、网络安全和游戏等多个领域中扮演着至关重要的角色。在这些领域中&#xff0c;代理IP与Socks5代理技术已经成为网络工程师的得力助手&#xff0c;本文将深入探讨它们在技术世界中的卓越应用。 1. 跨界电…...

kafka怎么实现零拷贝(Zero-Copy)的?

Kafka 实现零拷贝&#xff08;Zero-Copy&#xff09;主要依赖于操作系统和底层网络库的支持&#xff0c;而不是特定的算法。这是因为零拷贝是一种优化数据传输的技术&#xff0c;通常是通过操作系统和硬件来实现的。以下是 Kafka 如何实现零拷贝的一般原理&#xff1a; 直接内存…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...