代码随想录第29天|贪心算法part3

2024-06-16 15:36

本文主要是介绍代码随想录第29天|贪心算法part3,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

134.加油站

在这里插入图片描述
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈
每个加油站的剩余量rest[i]为gas[i] - cost[i]
从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置
因为我们一直维护的是一个剩余量大于等于0的区间,如果突然小于0,那么可以思考,从start到i中任取一个位置j作为起点,则j到i位置所得到的剩余量和一定小于0, 累加和cursum [start,j] > 0,[start,i] <0,而i>j,所以[j,i]必定<0
所以我们需要重新选择起始点,start=i+1,cursum=0,重新开始计算剩余量
在这里插入图片描述

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int cursum = 0;int totalSum = 0;int start = 0;for(int i = 0; i < gas.size(); i++){cursum += (gas[i] - cost[i]);totalSum += (gas[i] - cost[i]);if(cursum < 0){start = i + 1;cursum = 0;}}if(totalSum < 0) return -1;return start;}
};

135.分发糖果

在这里插入图片描述
这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。
局部最优:右边的孩子如果分数比左边大,就比左边多一颗
全局最优:相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果
但是单看右孩子还是无法满足题目条件,如
ratings:
[1,8,8,2,1]
光用右孩子会得到
[1,2,1,1,1]
这明显不满足条件,因为8比2大,2比1大,所以需要看左孩子
而且要从后向前遍历,因为r[i]和r[i-1]的比较要用上r[i]和r[i+1]的比较结果(糖果数)
如果 ratings[i] > ratings[i + 1],此时candyVec[i](第i个小孩的糖果数量)就有两个选择了,一个是candyVec[i + 1] + 1(从右边这个加1得到的糖果数量),一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。
局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。
取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多。

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candy(ratings.size(), 0);candy[0] = 1;for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1])candy[i] = candy[i - 1] + 1;elsecandy[i] = 1;}for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candy[i] = max(candy[i], candy[i + 1] + 1);}}int sum = 0;for (int m : candy) {sum += m;}return sum;}
};

860.柠檬水找零

在这里插入图片描述
记录收到的钞票数,如果是5元就拿着,10元就判断是否有5元剩余,
20元就首先判断有没有1个10元和1个5元,没有就判断有没有3个5元

class Solution {
public:bool lemonadeChange(vector<int>& bills) {vector<int> pay(3, 0);for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) {pay[0]++;} else if (bills[i] == 10) {if (pay[0] == 0)return false;pay[0]--;pay[1]++;} else {if (pay[0] == 0)return false;else {if (pay[1] != 0) {pay[1]--;pay[0]--;} else {if (pay[0] < 3)return false;elsepay[0] -= 3;}}}}return true;}
};

406.根据身高重建队列

在这里插入图片描述
遇到两个维度权衡的时候,一定要先确定一个维度,再确定另一个维度。
如果按照k来从小到大排序,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。

那么按照身高h来排序呢,身高一定是从大到小排(身高相同的话则k小的站前面),让高个子在前面。

此时我们可以确定一个维度了,就是身高,前面的节点一定都比本节点高!
首先按身高从高到低排序,然后从前往后遍历,如果有2个人比这个人高,则插入到下标为2的位置即可(前面两个人比他高)
在这里插入图片描述
局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优:最后都做完插入操作,整个队列满足题目队列属性

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {if (a[0] == b[0])return a[1] < b[1];return a[0] > b[0];});list<vector<int>> res;for (int i = 0; i < people.size(); i++) {int pos = people[i][1];auto it = res.begin();while(pos){it++;pos--;}res.insert(it,people[i]);}return vector<vector<int>>(res.begin(),res.end());}
};

这篇关于代码随想录第29天|贪心算法part3的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1066835

相关文章

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》:本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

nginx-rtmp-module模块实现视频点播的示例代码

《nginx-rtmp-module模块实现视频点播的示例代码》本文主要介绍了nginx-rtmp-module模块实现视频点播,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录预置条件Nginx点播基本配置点播远程文件指定多个播放位置参考预置条件配置点播服务器 192.

CSS自定义浏览器滚动条样式完整代码

《CSS自定义浏览器滚动条样式完整代码》:本文主要介绍了如何使用CSS自定义浏览器滚动条的样式,包括隐藏滚动条的角落、设置滚动条的基本样式、轨道样式和滑块样式,并提供了完整的CSS代码示例,通过这些技巧,你可以为你的网站添加个性化的滚动条样式,从而提升用户体验,详细内容请阅读本文,希望能对你有所帮助...

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT