每日OJ题_贪心算法三⑤_力扣134. 加油站

目录

力扣134. 加油站

解析代码


力扣134. 加油站

134. 加油站

难度 中等

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {}
};

解析代码

暴力解法:依次枚举所有的起点,从起点开始,模拟一遍加油的流程。

下面是暴力解法的代码(时间复杂度是O(N^2),会超时)

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; ++i){int diff = 0, step = 0;for(; step < n; ++step){int index = (i + step) % n; // 求出⾛ step 步之后的下标diff += gas[index] - cost[index];if(diff < 0)break;}if(diff >= 0) // 正常跳出return i;}return -1;}
};

        贪心优化:发现当从 i 位置出发,走了 step 步之后,如果失败了。那么 [i, i + step] 这个区间内任意一位置作为起点,都不可能环绕一圈(假设 i 位置有一个和暴力解法里面的diff,区间左边的diff肯定是大于0的,否则不能走到右边,如果减去左边的区间,从中间的区间某一个 i 开始,则肯定也是失败的,因为减的是大于0的)。因此枚举的下一个起点,应该是 i + step + 1 。

        只需在暴力的解法加上一句代码,时间复杂度就从O(N^2)变为O(N):

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; ++i){int diff = 0, step = 0;for(; step < n; ++step){int index = (i + step) % n; // 求出⾛ step 步之后的下标diff += gas[index] - cost[index];if(diff < 0)break;}if(diff >= 0) // 正常跳出return i;i += step; // i再++直接到step的后面->O(N)}return -1;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

CUDA-共享内存法实现矩阵乘法(比常规方案提速一倍)

作者&#xff1a;翟天保Steven 版权声明&#xff1a;著作权归作者所有&#xff0c;商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处 共享内存是什么&#xff1f; 共享内存是在多个处理单元之间共享数据的一种内存区域。在计算机体系结构中&#xff0c;共享内存通…

学QT的第二天~

小黑子鉴别界面 #include "mywidget.h" void MyWidget::bth1() { if(edit3 ->text()"520cxk"&&edit4 ->text()"1314520") { qDebug()<< "你好&#xff0c;真爱粉"; this->close(); } else { speecher->sa…

linux或ubuntu环境下需要自行安装vivado USB Program下载程序驱动

如果在linux或ubuntu环境下&#xff0c;不安装驱动是无法下载FPGA程序的。在linux或ubuntu环境下安装程序不要自动安装。 johnjohn-wang:~/vitis2021.2/Vivado/2021.2/data/xicom/cable_drivers/lin64/install_script/install_drivers$ sudo ./install_drivers

java—异常

异常 什么是异常 异常的体系 编译时异常处理方式 1、选择报错的整个代码块&#xff0c;快捷键crtlaltt键&#xff0c;选择try/catch将代码围起来。 2、编译异常处理方式2 在main方法上抛出异常 自定义异常 例子&#xff1a; 自定义运行时异常 自定义编译时异常 异常…

【快速幂取模】

求 a 的 b 次方对 p 取模的值&#xff0c;其中 1≤a,b,p≤109 输入 三个用空格隔开的整数a,b和p。 输出 一个整数&#xff0c;表示ab mod p的值。 样例输入 Copy 2 3 9样例输出 Copy 8 思路&#xff1a; 这里借鉴一下大佬的用例&#xff1a; #include<bits/stdc.h&…

【每日刷题】Day33

【每日刷题】Day33 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09; 2. 445. 两数相加 II - 力扣&#xff08;…

腾讯突然宣布,微信鸿蒙版要来了!

今年初&#xff0c;华为宣布HarmonyOS NEXT命名为“鸿蒙星河版”&#xff0c;并计划在二季度启动开发者 Beta 计划&#xff0c;四季度发布商用正式版。 消息一出&#xff0c;不少人为之振奋。 鸿蒙星河版因不再兼容安卓开源应用&#xff0c;仅支持鸿蒙内核和系统的应用&#x…

⚡REST 和 SOAP 协议有什么区别?

原文链接&#xff1a;https://document360.com/blog/rest-vs-soap/ API 是应用程序编程接口&#xff08;Application Programming Interface&#xff09;的缩写。API 规定了不同的软件组件应如何以编程方式进行交互和通信。 最常见的 API 类型就是 Web API。网络应用&#xff…

Scroll生态项目Penpad,再获Presto Labs的投资

Penpad是Scroll生态的LaunchPad平台&#xff0c;其整计划像收益聚合器以及RWA等功能于一体的综合性Web3平台拓展&#xff0c;该平台在近期频获资本市场关注&#xff0c;并获得了多个知名投资者/投资机构的支持。 截止到本文发布前&#xff0c;Penpad已经获得了包括Scroll联合创…

通信录的动态版本

一. 增加需求 在学习了动态开辟内存之后 我们对于通讯录产生了新的需求 要求我们做出一个动态增长的版本 即 随着我们储存联系人的增加 储存的空间增加 要求 &#xff1a; 1 初始空间为3 2 每次达到上限之后 扩容两个内存 二. 动手实施 我们首先要创建一个结构体 结构体…

领航法律科技,法大大多年深耕再获认可!

近日&#xff0c;“乘势破局 第八届新兴法律服务业高峰论坛”在上海隆重举行。作为国内领先的电子签厂商&#xff0c;法大大凭借在法律科技领域的多年深耕与沉淀&#xff0c;荣获“法律科技领航机构”称号。 据悉&#xff0c;新兴法律服务业高峰论坛作为国内首个聚焦“新兴法律…

每日一题(PTAL2):列车调度--贪心+二分

选择去维护一个最小区间 代码1&#xff1a; #include<bits/stdc.h> using namespace std; int main() {int n;cin>>n;int num;vector <int> v;int res0;for(int i0;i<n;i){cin>>num;int locv.size();int left0;int rightv.size()-1;while(left<…

【计组OS】访存过程以及存储层次化结构

苏泽 本专栏纯个人笔记作用 用于记录408 学习的笔记记录&#xff08;敲了两年码实在不习惯手写笔记了&#xff09; 如果能帮助到大家当然最好 但由于是工作后退下来备考 很多说法和想法都会结合实际开发的思想 可能不是那么的纯粹应试哈 希望大家挑选自己喜欢的口味食用…

什么牌子的骨传导耳机质量好?五大宝藏热门机型测评对比!

我作为一名音乐发烧友&#xff0c;对各类耳机产品都有深入的了解&#xff0c;最近也经常被人问及骨传导耳机哪个牌子好。通过交流&#xff0c;我发现很多人在选择骨传导耳机的时候&#xff0c;都有出现踩坑的情况&#xff0c;这也难怪&#xff0c;随着骨传导耳机热度逐渐增加&a…

【计算机毕业设计】基于SSM++jsp的网络游戏公司官方平台系统【源码+lw+部署文档+讲解】

目录 第1章 绪论 1.1 课题背景 1.2 课题意义 1.3 研究内容 第2章 开发环境与技术 2.1 MYSQL数据库 2.2 JSP技术 2.3 SSM框架 第3章 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2 经济可行性 3.1.3 操作可行性 3.2 系统流程 3.2.1 操作流程 3.2.2 登录流程 3.2.3 删除信息流…

【记录】Latex|解决 ACM-Reference-Format 顺序不符合论文实际引用顺序的问题

参考&#xff1a; Sort References by Order of Appearance with LaTeX/BibTeXOrdering reference in bibTex - StackOverflow 文章目录 问题描述解决方案 省流版解决方案 完整版《用LaTeX/BibTeX按出现顺序排序参考文献》1. 概述2. LaTeX 和 BibTeX3. 使用 LaTeX 进行参考文…

网站安全大揭秘:十大常见攻击方式与应对策略

随着互联网的普及&#xff0c;恶意内容攻击事件屡见不鲜。当一个网站遭遇恶意内容攻击时&#xff0c;不仅会影响用户体验&#xff0c;还可能对用户数据和隐私造成严重威胁&#xff0c;那么&#xff0c;网站都存在哪些形式的恶意攻击呢&#xff1f; 每种攻击的应对策略又是什么&…

PTQ4SAM、Mamba-Attention、AniTalker、IceFormer、U-DiTs、CogDPM

本文首发于公众号&#xff1a;机器感知 PTQ4SAM、Mamba-Attention、AniTalker、IceFormer、U-DiTs、CogDPM PTQ4SAM: Post-Training Quantization for Segment Anything Segment Anything Model (SAM) has achieved impressive performance in many computer vision tasks. Ho…

资源管理器CPU占用太高

最近资源管理器经常飙到80%-100%&#xff0c;所以电脑很卡。比如下面的新打开一个文件目录就这样 工具 shexview下载地址 排除 排序 先点Microsoft排序&#xff0c;上面粉色的就是所谓的外部插件 全部禁用 粉色全选->右键->Disable Selected Items &#xff08;看其他…