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

ops/2024/9/20 1:27:58/ 标签: 贪心算法, 算法

一、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/ops/7795.html

相关文章

Spring - 1 ( 8000 字 Spring 入门级教程 )

一&#xff1a;SpringBoot 快速上手 环境准备 ⾃检Idea版本: 社区版: 2021.1 -2022.1.4专业版: ⽆要求 如果个⼈电脑安装的idea不在这个范围, 需要卸载重新安装.&#xff08;⼀定要删除注册表&#xff09; Maven Maven是⼀个项⽬管理⼯具。基于POM(Project Object Model,…

centos 7.9 安装 ftp 传输文件

ftp server 端 sudo yum install vsftpd ftp其中 vsftpd 为 ftp server 端&#xff0c;ftp 包含 ftp 这个客户端命令。 # sudo rpm -ql vsftpd/etc/logrotate.d/vsftpd /etc/pam.d/vsftpd /etc/vsftpd /etc/vsftpd/ftpusers /etc/vsftpd/user_list /etc/vsftpd/vsftpd.conf /…

耀斑层-如何在Unity中实现耀斑亮光效果

在Unity中实现耀斑亮光效果可以通过以下步骤来实现&#xff1a; 创建一个空物体作为光源&#xff1a;在场景中创建一个空物体&#xff0c;并将其放置在需要发出耀斑亮光效果的位置上。 添加光源组件&#xff1a;选中空物体&#xff0c;在Inspector面板中点击"Add Compone…

C# 下记录(Record)详解

在C# 9.0中&#xff0c;引入了一个新的关键字&#xff1a;record。record关键字用于定义记录类型&#xff0c;这是一种不可变的数据结构&#xff0c;用于表示具有明确字段名称和类型的数据集。本文将详细介绍C#中record类型的使用和特点&#xff0c;以及如何通过记录记录器&…

使用easyexcel将csv转为excel

一.背景 供应商系统下载的csv文件不支持域控&#xff08;主要是第三方wps服务不能对csv文件加密&#xff0c;但是可以对office系列产品进行权限访问的加密控制&#xff09;。因此思路就改为现将csv文件转为excel文件&#xff0c;然后对excel文件进行加域控制。本文主要介绍如何…

数据结构--双向链表

在讲双向链表之前&#xff0c;我们先了解一下链表的分类&#xff1a; 链表的结构⾮常多样&#xff0c;主要分为带头与不带头、单向与双向、循环与不循环。三个种类可以任意搭配&#xff0c;所以总共可以形成八种链表&#xff0c;但是最常用的是单向不带头不循环链表和双向带头循…

html、css、QQ音乐移动端静态页面,资源免费分享,可作为参考,提供InsCode在线运行演示

CSDN将我上传的免费资源私自变成VIP专享资源&#xff0c;且作为作者的我不可修改为免费资源&#xff0c;不可删除&#xff0c;寻找客服无果&#xff0c;很愤怒&#xff0c;&#xff08;我发布免费资源就是希望大家能免费一起用、一起学习&#xff09;&#xff0c;接下来继续寻找…

代码托管基础操作

在待上传代码文件夹中右键&#xff0c;打开Git Bash Here依次输入以下命令&#xff1a; git init(在本地初始化一个代码仓库&#xff0c;具体表现为会在你的文件夹里出现一个隐藏的.git文件夹) git add .&#xff08;先把代码放到本地的一个缓冲区&#xff09;添加当前目录下的…

命理八字之答案之书前端uniapp效果实现

#uniapp# #答案之书# 不讲废话&#xff0c;先上截图 <div class"padding"><div class"flex align-center justify-center" style"padding-top:100px;"><div class"radarContainer"><div id"radarBox"…

初识ansible变量及实例配置

目录 1、为什么要使用变量 2、变量分类 3、 变量详解 3.1 vars,vars_files , group_vars 3.1 .1 vars 剧本中定义变量 3.1.2 vars_file 将变量存放到一个文件中&#xff0c;并在剧本中引用 3.1.3 group_vars 创建一个变量文件给某个组使用 实例1-根据不同的主机…

[ LeetCode ] 题刷刷(Python)-第35题:搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 nums 为 无重复元素 的 升序 排列数组 请必须使用时间复杂度为 O(log n) 的算法。 示例 示例 1: 输入: …

Django老项目升级到新版本

手上有个 Django 老项目&#xff0c;一直跑得好好的&#xff0c;好几年没动过了&#xff0c;维护费收得正爽&#xff0c;没想到客户来了个新的运营人员&#xff0c;丢了个改动需求过来。我一看也没啥大改&#xff0c;就答应了。大意了。 问题 刚开始改&#xff0c;我这种老鸟…

MongoDB聚合运算符:$sampleRate

MongoDB聚合运算符&#xff1a;$sampleRate 文章目录 MongoDB聚合运算符&#xff1a;$sampleRate语法使用举例 $sampleRate聚合运算符用$match&#xff0c;按照指定的抽样比例&#xff0c;从输入的文档中随机选择相应的文档。 语法 { $sampleRate: <non-negative float>…

使用Spring Boot整合定时任务(Schedule)

1、添加依赖&#xff1a; 在pom.xml文件中添加Spring Boot的定时任务依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter</artifactId> </dependency> 2、创建定时任务类&#xff1a; 创建…

搜索+剪枝,LeetCode 216. 组合总和 III

目录 一、题目 1、题目描述 2、接口描述 python3 cpp 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 python3 cpp 一、题目 1、题目描述 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多…

Linux下跟踪某个进程的内核处理时延消耗情况

1.利用系统自动的trace功能&#xff0c;编辑如下脚本&#xff0c;vim trace_process.sh #!/bin/sh cd /sys/kernel/debug/tracing/ #清空原有跟踪信息 echo > trace echo nop > current_tracer #设置要跟踪的进程 echo "pid281255" echo 281255 > set_ftra…

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现高并发服务器(TcpServer板块)

【项目】仿muduo库One Thread One Loop式主从Reactor模型实现⾼并发服务器&#xff08;TcpServer板块&#xff09; 一、思路图二、模式关系图三、定时器的设计1、Linux本身给我们的定时器2、我们自己实现的定时器&#xff08;1&#xff09;代码部分&#xff08;2&#xff09;思…

ASP.Net MVC 登录页面实现RSA非对称加密

一、什么是RSA非对称加密 RSA是1977年由罗纳德李维斯特&#xff08;Ron Rivest&#xff09;、阿迪萨莫尔&#xff08;Adi Shamir&#xff09;和伦纳德阿德曼&#xff08;Leonard Adleman&#xff09;一起提出的。 RSA算法是一种非对称加密算法&#xff0c;与对称加密算法不同…

【CSS】CSS实现元素逐渐消失(实现元素透明逐渐消失/模糊)

mask-image: linear-gradient(to bottom, rgba(0, 0, 0, 0) 0%, rgba(0, 0, 0, 1) 10%);mask-image 属性用于定义一个遮罩&#xff0c;它可以隐藏元素的一部分或全部内容。在这个示例中&#xff0c;我们使用 mask-image 属性来定义一个线性渐变的遮罩&#xff0c;使得列表项的内…

达梦数据库执行sql报错:数据溢出

数据库执行sql报错数据溢出 单独查询对应的数字进行计算是不是超过了某个字段类型的上限或下限 如果已经超过了&#xff0c;进行对字段进行cast类型转换处理&#xff0c;转换为dec num都可以尝试 这里就是从 max(T.BLOCK_ID as dec*8192t.bytes)/1024/1024 max_MB,换成了这个…