leecode134.加油站

embedded/2024/11/24 7:15:30/

 一开始想的是总体上加油量超过耗油量那么就一定能找到一个起始点可以跑一圈,这个起始点选择补充油量与耗油量差值最大的那gas个点,但是我没仔细审题,这个起始点是索引逐次+1绕一圈而不是随便选择,gas[5,8,2,8],cost[6,5,6,6]这里错误地选择了1为起点

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int result=-1;int difference=INT32_MIN;int differenceSum=0;int n=gas.size();for(int i=0;i<n;i++){int temp=gas[i]-cost[i];if(temp>difference){difference=temp;result=i;}differenceSum+=temp;}if(differenceSum<0)return -1;elsereturn result;}
};

 改进方法是累加每次剩余油量,如果在i处剩余油量为负数那么不能选择i及之前的作为起始点,转战i+1,剩余油量变为0

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int result=0;int difference=0;int differenceSum=0;int n=gas.size();for(int i=0;i<n;i++){int temp=gas[i]-cost[i];differenceSum+=temp;difference+=temp;if(difference<0){result=i+1;difference=0;}}if(differenceSum<0)return -1;elsereturn result;}
};


http://www.ppmy.cn/embedded/140061.html

相关文章

使用 Java Stream 优雅实现List 转化为Map<key,Map<key,value>>

使用 Java Stream 优雅实现List 转化为Map<key,Map<key,value>> 问题背景 在开发中&#xff0c;我们经常需要根据某些规则对数据进行分组并构造成嵌套 Map。本例以学生信息为背景&#xff0c;展示如何用 Stream API 实现按班级分组并嵌套为以学生 ID 为键的 Map。…

2023年9月GESPC++一级真题解析

一、单选题&#xff08;每题2分&#xff0c;共30分&#xff09; 题号 123456789101112131415 答案 CDBCDBACACBBDDA 1. 我们通常说的 “ 内存 ” 属于计算机中的&#xff08;&#xff09;。 A. 输出设备 B. 输 ⼊ 设备 C. 存储设备 D. 打印设备 【答案】 C 【考纲知识点】…

【AIGC】ChatGPT提示词Prompt解析:文章创作大师

后续会发布进阶Prompt&#xff0c;大家点个免费的【关注】吧 引言 在当今信息爆炸的时代&#xff0c;如何让内容创作既保持原创性又提升效率&#xff0c;成为一个重要课题。文章创作助手应运而生&#xff0c;它不仅是一个简单的改写工具&#xff0c;更是一个能深入理解内容DNA…

hhdb数据库介绍(10-3)

集群管理 单机部署 单机部署为管理平台为用户提供单个组件安装部署的功能&#xff0c;弥补集群部署功能中无法单独安装某个组件的缺陷。具体功能说明与操作步骤请参考安装部署文档。 部署环境体检 部署评分体检是一套专门为计算节点群量身打造的运行环境体检评分功能。用户…

常见面试题----深入源码理解MQ长轮询优化机制

引言 在分布式系统中&#xff0c;消息队列&#xff08;Message Queue, MQ&#xff09;扮演着至关重要的角色。MQ不仅实现了应用间的解耦&#xff0c;还提供了异步消息处理、流量削峰等功能。而在MQ的众多特性中&#xff0c;长轮询&#xff08;Long Polling&#xff09;机制因其…

springboot购物推荐网站的设计与实现(代码+数据库+LW)

摘要 随着信息互联网购物的飞速发展&#xff0c;一般企业都去创建属于自己的电商平台以及购物管理系统。本文介绍了东大每日推购物推荐网站的开发全过程。通过分析企业对于东大每日推购物推荐网站的需求&#xff0c;创建了一个计算机管理东大每日推购物推荐网站的方案。文章介…

微信小程序中会议列表页面的前后端实现

题外话&#xff1a;想通过集成腾讯IM来解决即时聊天的问题&#xff0c;如果含语音视频&#xff0c;腾讯组件一年5万起步&#xff0c;贵了&#xff01;后面我们改为自己实现这个功能&#xff0c;这里只是个总结而已。 图文会诊需求 首先是个图文列表界面 同个界面可以查看具体…

计算机网络:运输层 —— TCP 的超时重传机制

文章目录 TCP 的超时重传超时重传时间的选择重传策略与拥塞控制的关联 TCP 的超时重传 TCP 的超时重传是保证数据可靠传输的重要机制之一 保证数据可靠性&#xff1a;通过超时重传机制&#xff0c;即使在网络状况不佳&#xff0c;出现数据包丢失等情况时&#xff0c;也能够确保…