LeetCode 热题 100 | 贪心算法

目录

1  121. 买卖股票的最佳时机

2  55. 跳跃游戏

3  45. 跳跃游戏 II

4  763. 划分字母区间


菜鸟做题,语言是 C++

1  121. 买卖股票的最佳时机

解题思路:

  • 维护一个变量 max_price
  • max_price 用于存储排在 i 天之后的股票最高价格
  • 第 i 天的最高利润 = max_price - 第 i 天的股票价格

思路说明:

假设股票价格数组为 [7,1,5,3,6,4],从后往前遍历数组以计算 max_price,如下图所示。

1)如果第 i 天的股票价格低于 max_price,则

  • 第 i 天的最高利润 = max_price - 第 i 天的股票价格
  • 需要更新 profit
  • 不需要更新 max_price

2)如果第 i 天的股票价格高于 max_price,则

  • 第 i 天的最高利润 = 0
  • 不需要更新 profit
  • 需要更新 max_price

在如下代码中,我用的是变量 ans 代表 profit 的含义。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ans = 0, max_price = 0;for (int i = n - 1; i >= 0; --i) {if (prices[i] > max_price) {max_price = prices[i];} else {ans = max(ans, max_price - prices[i]);}}return ans;}
};

2  55. 跳跃游戏

解题思路:

  • 遍历 nums 数组
  • 不断更新最远距离 maxDistance
  • 如果 maxDistance >= nums.size() - 1,则返回 true

思路说明图:

  1. 遍历第 0 个元素,maxDistance = 2
  2. 遍历第 1 个元素,maxDistance = 1 + 3 = 4
  3. 遍历第 2 个元素,maxDistance = 4(> 2 + 1)
  4. 以此类推
class Solution {
public:bool canJump(vector<int>& nums) {int maxDistance = 0;for (int i = 0; i < nums.size(); ++i) {if (i <= maxDistance) {maxDistance = max(i + nums[i], maxDistance);}}return maxDistance >= nums.size() - 1;}
};

3  45. 跳跃游戏 II

解题思路:

  • 仍然是遍历 nums 数组,每次更新 maxDistance 范围
  • 针对在同一次更新后被包含进去的位置,算作一次跳跃

思路说明图:

将 maxDistance 初始化为 0,被包含进去的 0 号位置,属于第一次跳跃(count = 0)。根据 0 号位置更新 maxDistance 为 2,被包含进去的 1、2 号位置,属于第二次跳跃(count = 1)。根据 1、2 号位置更新 maxDistance 为 4,被包含进去的 3、4 号位置,属于第三次跳跃(count = 2)。

如果更新 maxDistance 后发现 maxDistance >= nums.size() - 1,则返回 count + 1 即可。为什么是 count + 1?因为目前只是能够跳跃到达 nums.size() - 1,但还没有跳。

class Solution {
public:int jump(vector<int>& nums) {int maxDistance = 0;int pos = 0, count = 0;if (pos >= nums.size() - 1)return 0;while (pos < nums.size()) {int temp = maxDistance;while (pos <= temp) {maxDistance = max(maxDistance, pos + nums[pos]);if (maxDistance >= nums.size() - 1) {return count + 1;}++pos;}++count;}return count;}
};

4  763. 划分字母区间

解题思路:

  • 遍历字符串 s,记录每个字母的最后出现位置
  • 设置 begin = 0,即从 0 号字母开始划分字符串
  • 根据每个字母的最后出现位置不断更新 end
  • 若当前位置 = end,则 begin ~ end 之间是一个子串

思路说明图:

  • 图中的 B 代表 begin,即子串的开头;E 代表 end,即子串的结尾
  • 初始化 begin 为 0,初始化 E 为第一个字母的最后出现位置

我们需要保证的是 B 和 E 之间的所有字母不能横跨两个子串。换句话说,B 和 E 之间的 b 和 c 的最后出现位置不能超过 a 的最后出现位置 E 。如果超过了,我们需要更新 E 。

第一轮:首先访问 a,并且设置 E 为 a 的最后出现位置;接着访问 b,由于 b 的最后出现位置没有超过 E,因此不需要更新 E。以此类推访问到 c,由于 c 的最后出现位置没有超过 E,因此不需要更新 E 。最后指针 i 移动到 E,说明 B 和 E 之间的字母只会出现在该区间内,由此得到第一个子串。

第二轮:B 更新到 E 的后面一个位置,模仿第一轮的操作继续访问。

由于篇幅有限,因此图中省略了一些步骤,请自行脑补。

class Solution {
public:vector<int> partitionLabels(string s) {unordered_map<char, int> charEnd;for (int i = 0; i < s.size(); ++i) {charEnd[s[i]] = i;}vector<int> ans;int begin = 0, end = 0;for (int i = 0; i < s.size(); ++i) {end = max(end, charEnd[s[i]]);if (i == end) {ans.push_back(end - begin + 1);begin =  end + 1;}}return ans;}
};

上述代码用的是哈希表 charEnd 来存储字母的最后出现位置,换成 vector<int> 也行。

这样做会超出内存限制:

int subStrEnd = charEnd[s[0]];
while (begin < s.size()) {while (end <= subStrEnd) {subStrEnd = max(subStrEnd, charEnd[s[end]]);++end;}ans.push_back(end - begin);begin = end;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/298286.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】:深入解析多表查询(上)

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; MySQL从入门到进阶 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一. 多表关系1.1 一对多1.2 多对多1.3 一对一 二. 多表查询概述2.1 概述2.2 分类…

升级一下电脑,CPU换I5-14600K,主板换华硕B760M

刚给自己电脑升级了一下&#xff0c;CPU从 AMD R5 5600X 换成 Intel I5-14600K&#xff0c;主板换成了华硕的 TUF GAMING B760M-PLUS WIFI D4。 因为我现有的两根内存是DDR4的&#xff0c;所有我选了个支持DDR4内存的主板。 我发现用AMD处理器时将系统从Win10升级到Win11后变…

基于SSM的邮票鉴赏系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的邮票鉴赏系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Spri…

frp内网穿透,让外网可以访问内网

需求 我们的svn部署在内网&#xff0c;用的一直没问题&#xff0c;但是有时候有需求在外网访问svn&#xff0c;进行提交更新等操作&#xff0c;这时候就有了内网穿透这个需求。 当然&#xff0c;我们也可以借助花生壳等软件进行内网穿透&#xff0c;傻瓜化操作&#xff0c;也…

Yarn的安装和使用(2):使用及问题解决

Yarn是JavaScript的依赖管理工具&#xff0c;它与npm类似&#xff0c;但提供了一些额外的性能优化和一致性保证。 Yarn的使用&#xff1a; 初始化项目&#xff1a; yarn init 此命令会引导您创建一个新的package.json文件&#xff0c;用于记录项目的元信息和依赖。 添加依赖&…

如何更新Code::blocks的MinGW

前言 LVGL V9版本更新了很多新特性&#xff0c;其中windows平台部分也进行了优化&#xff0c;如果你是用的是Code::blocks体验LVGL那么在编译时会不通过&#xff1b;因为如果你使用的是 Code::blocks 20.03并且使用内置的MinGW&#xff0c;那么就会因为MinGW版本过低遇到下面所…

c++的学习之路:12、vector(1)

这章主要是根据cplusplus中的文档进行使用Vector&#xff0c;文章末附上测试代码。 目录 一、什么是vector 二、vector的简单使用 三、代码 一、什么是vector 下图是cplusplus的简介&#xff0c;上面一共有六点&#xff0c;如下&#xff1a; 1、vector是表示可变大小数组…

Ant Design Vue table固定列失效问题解决

问题描述&#xff1a;项目中封装好的公共table组件&#xff0c;基于Ant Design Vue table封装&#xff1b;使用中&#xff0c;用到了列固定&#xff0c;但是没生效&#xff0c;找了好久的原因。。。最后是因为外层容器标签导致&#xff1b; 解决方法&#xff1a;如果a-table组件…

Linux: linux常见操作指令

目录 01.ls 指令 02. pwd命令 03. cd 指令 04. touch指令 05.mkdir指令&#xff08;重要&#xff09; 06.rmdir指令 && rm 指令&#xff08;重要&#xff09; 07.man指令&#xff08;重要&#xff09; 07.cp指令&#xff08;重要&#xff09; 08.mv指令&#…

理解 SQL 数据添加:从基础到实践

引言&#xff1a; 在现代软件开发中&#xff0c;数据库是不可或缺的一部分。而 SQL 作为结构化查询语言的代表&#xff0c;广泛应用于数据库管理系统中&#xff0c;为我们提供了强大的数据管理和查询能力。 主题&#xff1a; 我们将从基础的 SQL INSERT INTO 语句开始&…

EVM Layer2 主流解决方案

深度解析主流 EVM Layer 2 解决方案&#xff1a;zk Rollups 和 Optimistic Rollups 随着以太坊网络的不断演进和 DeFi 生态系统的迅速增长&#xff0c;以太坊 Layer 2 解决方案日益受到关注。 其中&#xff0c;zk Rollups 和 Optimistic Rollups 作为两种备受瞩目的主流 EVM&…

地质地貌卫星影像集锦(三 矿产资源篇)

1. 元古代沉积岩的抬升 这个地区位于Leigh Creek中部&#xff0c;距离澳大利亚南部的阿德莱德约500km&#xff0c;弗林德斯山脉的北面是Gawler克拉通。弗林德斯山脉是由元古代沉积岩抬升后形成的块体&#xff0c;在其之下的是寒武纪的岩石&#xff0c;它座落在距阿德莱德北…

How to install JDK on mac

文章目录 1. Install JDK on mac2. zshenv, zshrc, zprofile3. 查看java环境变量配置 1. Install JDK on mac Installation of the JDK on macOS 2. zshenv, zshrc, zprofile How Do Zsh Configuration Files Work? 3. 查看java环境变量配置 open Terminal&#xff0c;cd…

HTTP 常见面试题(计算机网络)

HTTP 基本概念 一、HTTP 是什么&#xff1f; HTTP(HyperText Transfer Protocol) &#xff1a;超文本传输协议。 HTTP 是一个在计算机世界里专门在「两点」之间「传输」文字、图片、音频、视频等「超文本」数据的「约定和规范」。 「HTTP 是用于从互联网服务器传输超文本到本…

虚拟机打不开

问题 另一个程序已锁定文件的一部分&#xff0c;进程无法访问 打不开磁盘“G:\centeros\hadoop104kl\hadoop100-cl2.vmdk”或它所依赖的某个快照磁盘。 模块“Disk”启动失败。 未能启动虚拟机。 原因 前一次非正常关闭虚拟机导致.lck 文件是VMWare软件的一种磁盘锁文件&…

【java探索之旅】逻辑控制掌握 顺序结构 分支语句

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Java编程秘籍 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一、逻辑控制的概念二、顺序结构三、分支结构3.1 if语句3.2 if习题巩固3.3 细节注意项…

【QT+QGIS跨平台编译】056:【pdal_lepcc+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

点击查看专栏目录 文章目录 一、pdal_lepcc介绍二、pdal下载三、文件分析四、pro文件五、编译实践一、pdal_lepcc介绍 pdal_lepcc 是 PDAL(Point Data Abstraction Library)的一个插件,用于点云数据的压缩。它基于 EPCC(Entwine Point Cloud Compression)算法,提供了对点…

【C++】list模拟实现

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. list源码3. 初始化3.1 构造3.2 拷贝构造3.3 赋值3.4 析构 4. 迭代器4.1 后置加加和前置加加4.2 后置减减和前置减减4.3 解引用4.4 &#xff01;和4.5 begin 和 end4.6 const迭代器4.7 迭代器优化 5. Modifi…

深入浅出 -- 系统架构之微服务中OpenFeign最佳实践

前面我们讲了一下 Ribbon 和 RestTemplate 实现服务端通信的方法&#xff0c;Ribbon 提供了客户端负载均衡&#xff0c;而 RestTemplate 则对 http 进行封装&#xff0c;简化了发送请求的流程&#xff0c;两者互相配合&#xff0c;构建了服务间的高可用通信。 但在使用后也会发…

C++入门(以c为基础)——学习笔记2

1.引用 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变量开辟内存空 间。在语法层面&#xff0c;我们认为它和它引用的变量共用同一块内存空间。 可以取多个别名&#xff0c;也可以给别名取别名。 b/c/d本质都是别名&#…