134. 加油站(贪心算法)

根据题解
这道题使用贪心算法,找到当前可解决问题的状态即可

「贪心算法」的问题需要满足的条件:

  1. 最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定;
  2. 无后效性:后面阶段的求解不会修改前面阶段已经计算好的结果;
  3. 贪心选择性质:从局部最优解可以得到全局最优解。

如果要求走一圈,则总剩余油量total应该大于等于0
而在每个站点的时候,当前剩余油量curr如果大于等于0,代表可以到达下一个站点,如果小于0,代表从当前及之前的站点出发无法到达下一个站点,于是出发点改为下一个站点。
为什么说当前及之前的站点出发都无法到达下一个站点呢?
参考这个题解的图:
在这里插入图片描述

可以看到,假设start已经更改为3之后,可以到达4,假设到下一个节点时,cursum变成了负数,而在这之前的两个站点的cursum都是正数,代表它俩的加和都不够,更别提其中一个了 ,所以start会跳过4,更新为i+1

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥第一期模拟总结

文章目录 1.动态的 Tab 栏2.地球漫游3.迷惑的this4.燃烧卡路里5.魔法失灵了6.年龄统计 所有题目链接 1.动态的 Tab 栏 本题要实现一个tab栏固定效果&#xff0c;看见题目就想到css中的 position: fixed; 尝试了很久都没能实现效果&#xff0c;后来又想到了粘性定位 position: …

【深度学习】深度学习框架的环境配置

目录 1. 配置cuda环境 1.1. 安装cuda和cudnn 1.1.1. 显卡驱动配置 1.1.2. 下载安装cuda 1.1.3. 下载cudnn&#xff0c;将解压后文件复制到cuda目录下 1.2. 验证是否安装成功 2. 配置conda环境 2.1. 安装anaconda 2.2. conda换源 2.3. 创建conda环境 2.4. pip换源 3…

封装员工头像组件

创建image-upload组件 <template><el-uploadclass"avatar-uploader"action"":show-file-list"false":before-upload"beforeAvatarUpload"><!-- (自动上传)action是上传地址 --><img v-if"value" :s…

第二次量子化

专栏目录: 高质量文章导航-持续更新中 前置复盘: 玻色子和费米子: 首先,我们希望把描述单粒子态的量子力学推广到全同多粒子体系。我们的做法是从单粒子态的希尔伯特空间(Hilbert Space)出发,构造全同多粒子态的态空间——福克空间(Fock Space),它实际上就是无穷个…

20231202 VCSA 7.0 日志清理及空间扩容

日志清理 ssh 到 VCSA 上&#xff0c;输入 shell 进入控制台 df -lh 查看空间大小&#xff0c;发现 /storage/archive 占据空间比较大&#xff0c;这里应该是备份日志的地方&#xff0c;里边文件不大但很多&#xff0c;查找并删除 30 天以前的日志 cd /storage/archive/vpostgr…

对于Windows就是找不到 环境变量 的解决

我认为将“我的电脑”从桌面上隐藏掉纯粹是傻逼行为 说下解决办法&#xff1a; 1. 找到文件资源管理器&#xff0c; 2. 右键点击“此电脑” -- 选择属性&#xff1a; 3. 进入属性界面&#xff0c;应该进入的是“关于”界面&#xff1a;选择“高级系统设置”&#xff1a; 4. 终…

更有效的问卷发布方法与必备问卷工具推荐

问卷怎么发&#xff1f;通过哪些渠道发&#xff1f;怎么发收集的数量更多&#xff1f;怎么获得有效数据&#xff1f;这些是做问卷的调查人员经常会遇到的问题。的确&#xff0c;问卷的发放是否有效不仅会影响到收集数据的体量&#xff0c;更会影响到最终结论的真实性。所以&…

ssm+vue的罪犯信息管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频&#xff1a; ssmvue的罪犯信息管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;ssm vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…

12月02日每日信息差

_灵感 &#x1f396; 六国入境免签首日2029人次享便利 &#x1f384; 国内首个超大规模“光伏气膜”项目在江苏投运 &#x1f30d; 东京将推出氢气交易市场 &#x1f30b; 中国疾控中心&#xff1a;建议尽早接种流感疫苗&#xff0c;尤其是老年人和儿童 &#x1f381; 偏高1.…

CCC联盟数字车钥匙(七)——BLE连接流程

本文接上一篇CCC数字钥匙BLE概述&#xff0c;介绍BLE中相关连接流程的实现。 2、BLE流程 2.1 所有者配对连接建立 CCC中使用Bluetooth OOB&#xff08;Out of Band, 带外&#xff09;配对完成所有者配对、连接建立的流程。BLE设置分为以下两个子部分&#xff1a; BLE链路层连…

根目录/ 空间不够,扩容,导致web页面无法加载问题

现象就是&#xff1a;搭建的web页面无反应&#xff0c;也没报错&#xff0c;怀疑是内存空间不够导致的。/ 扩容步骤如下&#xff1a; 虚拟机为关机状态添加虚拟磁盘 #查看磁盘&#xff0c;并创建新分区 fdisk -l fdisk /dev/sdb p       查看已分区数量&#xff08;我看…

C# 将CSV文件内容装配成对象列表

写在前面 CSV文件采用纯文本的存储形式&#xff0c;字段间以分隔符进行区分&#xff0c;行之间以换行符进行切换&#xff0c;既可以用文本编辑器打开也可以用Excel编辑&#xff0c;可读性非常好&#xff0c;在游戏开发领域经常将其作为数值配置文件使用。文本编辑器推荐EmEdit…

msvcp140_codecvt_ids.dll丢失解决方案,验证有效

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“msvcp140_codecvt_ids.dll丢失”。这些动态链接库文件是程序运行所必需的&#xff0c;它们包含了许多函数和资源。丢失或者损坏通常会导致某些应用程序无法正常运行。 首先&#xff0c;我们…

LangChain(0.0.340)官方文档三:Prompts上——自定义提示模板、使用实时特征或少量示例创建提示模板

文章目录 一、 Prompt templates1.1 langchain_core.prompts1.2 PromptTemplate1.2.1 简介1.2.2 ICEL1.2.3 Validate template 1.3 ChatPromptTemplate1.3.1 使用role创建1.3.2 使用MessagePromptTemplate创建1.3.3 自定义MessagePromptTemplate1.3.3.1 自定义消息角色名1.3.3.…

Nat. Rev. Chem. | 一份关于用机器学习研究化学问题的评估指导

今天为大家介绍的是来自Tiago Rodrigues团队的一篇论文。机器学习&#xff08;ML&#xff09;有望解决化学领域的重大挑战。尽管ML工作流程的适用性极广&#xff0c;但人们通常发现评估研究设计多种多样。目前评估技术和指标的异质性导致难以&#xff08;或不可能&#xff09;比…

redisson分布式锁

一、分布式锁 java里面的锁机制针对的是同一个jvm进程进行共享资源的共享加锁&#xff0c;但在分布式系统中&#xff0c;一般一个服务都会部署多个节点&#xff0c;这种情况下就需要有单独的中间件来承担多节点间加锁的责任。 二、使用案例 // 1. 获取锁对象RLock lock redi…

一篇带你串通数据结构

文章目录 导论数据结构的定义数据结构在计算机科学中的重要性为什么学习数据结构很重要 1、基本概念1.1、数据、数据元素和数据项的概念1.2、数据对象与数据结构的关系1.3、逻辑结构与物理结构 2、线性结构2.1、数组2.2、链表2.3、栈2.4、队列 3、非线性结构3.1、树3.2、图 4、…

在oracle中的scn技术

SCN可以说是Oracle中一个很基础的部分&#xff0c;但同时它也是一个很重要的。它是系统中维持数据的一致性和顺序恢复的重要标志&#xff0c;是数据库非常重要的一种数据结构。 转载&#xff1a;深入剖析 - Oracle SCN机制详细解读 - 知乎 (zhihu.com)https://zhuanlan.zhihu.…

【LeetCode】135. 分发糖果

135. 分发糖果 文章目录 一、贪心1.1 贪心 二、多语言解法 参考图解 先按「左规则」得到下图&#xff1a; 再按「右规则」处理后如下图&#xff1a; 最终&#xff0c;取 max&#xff08;左规则&#xff0c;右规则&#xff09;&#xff0c;才能同时满足左规则和右规…

【slab/0x40 UAF】TPCTF2023 - core 一题多解

前言 这题据说比赛被非惨了&#xff0c;但是笔者比较菜&#xff0c;比赛的时候没有正规做出来并且也没有发现非预期&#xff0c;乐。其实比赛的时候一直在纠结为啥 free obj 没有 freelist&#xff0c;哎&#xff0c;陷进去了&#xff0c;我的 Root 宝贝。 笔者赛后用两种【常…