代码随想录训练营24day-贪心算法2

devtools/2024/11/14 12:40:33/

一、122 买卖股票最佳时机

题目介绍限制条件,必须卖了再买,而且当前交易一只股票。一开始想法是去遍历,找到每个区间段间的差值,然后再相加。看了解答,其实每一天的利润,都是可以用差值表示出来,每一天的利润最大,那么累加起来,总利润也是最大的。再思考怎么能最大化,只要每天的是正利润,那么就是递增的。

int maxProfit(int* prices, int pricesSize) {//可以计算每天的利润int result = 0;for(int i = 1; i < pricesSize; i++){int diff = prices[i] - prices[i - 1];//每一天的正利润相加if(diff >= 0){result += diff;}}return  result;
}

二、55 跳跃游戏

题目意思是从下标index=0(第一个位置),跳跃数组上指定范围内的步数,能不能跳跃到最后一步。

每一步所在的数组值都是一个跳跃范围,代表了在此时,这个点能够达到的最大范围。再跳跃到最大范围的点上,找到此位置上的值,来确认范围是否覆盖。

每一次遍历数组,找到num[i] + i是不是最大值,每一次都更新最大值,判断最大值是不是到达边界。

bool canJump(int* nums, int numsSize) {int pos = 0;if(numsSize == 1){return true;}//注意这里是<= posfor(int i = 0; i <= pos; i++){pos = pos > i + nums[i] ? pos : i + nums[i];//printf("pos %d i%d  \n", pos, i);if(pos >= numsSize -1){return true;}}return false;
}

三、45 跳跃游戏II

题目明确是能到达最后一个位置,求最小的步骤。

最少的步骤,就是每一步尽量选择最大的步长,且选择的位置 + 步长能够覆盖到最后一个位置。

 注意:真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!

遍历整个数组,拿到最远覆盖范围(每一次遍历需要更新),如果i到达上一次的最远范围,把当前最远范围给pre上一次最远范围。移动次数加1,如果当前最远范围已经能覆盖最后一个位置,那么就退出;

int jump(int* nums, int numsSize) {int next = 0;int cur = 0;int result = 0;for(int i = 0; i < numsSize; i++){next = next > nums[i] + i? next : nums[i] + i;if(i == cur){result++;cur = next;if(next >= numsSize - 1){break;}}}return result;
}


http://www.ppmy.cn/devtools/6477.html

相关文章

STL::string简单介绍

目录 1、什么是STL STL6大组件:仿函数、算法、容器、空间配置器、迭代器、配接器 推荐文档&#xff08;必须学会看文档&#xff09; 2、string常用接口 a、初始化 1、什么是STL 标准模板库 STL&#xff08;Standard Template Library&#xff09;&#xff0c;主要是数据结构…

云原生:10分钟了解一下Kubernetes架构

Kubernetes&#xff0c;作为当今容器编排技术的事实标准&#xff0c;以其强大的功能和灵活的架构设计&#xff0c;在全球范围内得到了广泛的应用和认可。本文将深入简出地探讨Kubernetes的核心架构&#xff0c;帮助大家了解Kubernetes&#xff0c;为今后的高效的学习打下良好的…

达梦数据库一体机树立金融解决方案标杆

达梦数据库一体机自问世以来&#xff0c;获得众多行业用户的高度关注&#xff0c;并率先在金融行业吹响冲锋号角&#xff0c;实现多个重大项目的落地应用。近日&#xff0c;珠海华润银行股份有限公司基于达梦数据库一体机 I 系列的《数据库一体机银行多业务系统集中部署解决方案…

BGP边界网关路由实验(华为)

思科设备参考&#xff1a;BGP边界网关路由实验&#xff08;思科&#xff09; 一&#xff0c;技术简介 BGP&#xff08;边界网关路由协议&#xff09;是一种自治系统&#xff08;AS&#xff09;间的协议&#xff0c;主要用于在不同的AS之间交换路由信息。AS是一个由一组网络设…

Linux小知识:xargs命令的使用与技巧

在Linux系统中&#xff0c;命令行工具是用户与系统进行交互的重要桥梁。其中&#xff0c;xargs命令是一个非常实用的工具&#xff0c;它能够将标准输入的数据转换为命令行参数&#xff0c;从而方便用户对数据进行批量处理。今天&#xff0c;我们就来详细了解一下xargs命令的使用…

Go 语言中的 GIF 图像处理完全指南:`image/gif`的技术与实践

Go 语言中的 GIF 图像处理完全指南&#xff1a;image/gif的技术与实践 概述安装与基础设置导入 image/gif 包初步配置示例&#xff1a;设置一个简单的 GIF 编码环境 读取与解码 GIF 图像读取 GIF 文件解析 GIF 数据 创建与编码 GIF 图像创建 GIF 图像编码 GIF 图像 处理 GIF 动…

鸿蒙入门05-真机运行“遥遥领先”

如果你有一台真的 "遥遥领先"那么是可以直接在手机上真机运行你的项目的我们也来尝试一下运行 一、手机设置开发者模式 打开手机设置 打开手机设置界面 向下滑动到关于手机位置 快速连续点击版本号位置 下图所示位置快速连续点击 打开 3 - 5 次即可 会提示您已经进…

C++学习————第八天(C/C++内存管理)

目录 1、1.C/C内存分布 2、 C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3、C内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 4.operator new与operator delete函数 5. new和delete的实现原理 5.1 内置类型 5.2 自定…