加油站(力扣134)

news/2025/2/23 10:49:59

既然每一个加油站都有对应的加油量和耗油量,我们不妨计算一下每个加油站的汽油净增量。如果每个加油站净增量之和不为负数,则说明一定可以找到唯一的起始点。那我们该如何找到这个起始点呢?我们设置最开始的起点为第0个加油站,接着通过for循环往后遍历每一个加油站,同时将每个加油站的净增量逐个累加。在这个过程中我们运用贪心思想:当汽油净增量之和为负数时,我们就可以将起始点更新到当前加油站的下一位。大家可以结合我下面的代码及详细注释理解此题。

代码及详细注释如下:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> sum(gas.size() + 1);
        //计算每个加油站的油量净增多少
        for(int i = 0;i < gas.size();i++){
            sum[i] = gas[i] - cost[i];
        }
        int total = 0;
        for(int i = 0;i < sum.size();i++){
            total += sum[i];
        }
        //用全局视先判断问题是否存在解
        if(total < 0) return -1;
        int Cursum = 0;
        int start = 0;
        for(int i = 0;i < sum.size();i++){
            Cursum += sum[i];
        //当前汽油为负数时,就要将下一位设置为新的start
            if(Cursum < 0){
        //记得清0当前汽油量
                Cursum = 0;
                start = i + 1;
                continue;
            }
        }
        return start;
    }
};


http://www.niftyadmin.cn/n/5863341.html

相关文章

25轻化工程研究生复试面试问题汇总 轻化工程专业知识问题很全! 轻化工程复试全流程攻略 轻化工程考研复试真题汇总

轻化工程复试心里没谱&#xff1f;学姐带你玩转面试准备&#xff01; 是不是总觉得老师会问些刁钻问题&#xff1f;别焦虑&#xff01;其实轻化工程复试套路就那些&#xff0c;看完这篇攻略直接掌握复试通关密码&#xff01;文中有重点面试题可直接背~ 目录 一、这些行为赶紧避…

七星棋牌顶级运营产品全开源修复版源码教程:6端支持,200+子游戏玩法,完整搭建指南(含代码解析)

棋牌游戏一直是移动端游戏市场中极具竞争力和受欢迎的品类&#xff0c;而七星棋牌源码修复版无疑是当前行业内不可多得的高质量棋牌项目之一。该项目支持 6大省区版本&#xff08;湖南、湖北、山西、江苏、贵州&#xff09;&#xff0c;拥有 200多种子游戏玩法&#xff0c;同时…

第16届蓝桥杯模拟赛3 python组个人题解

第16届蓝桥杯模拟赛3 python组个人题解 思路和答案不保证正确 1.填空 如果一个数 p 是个质数&#xff0c;同时又是整数 a 的约数&#xff0c;则 p 称为 a 的一个质因数。 请问&#xff0c; 2024 的最大的质因数是多少&#xff1f; 因为是填空题&#xff0c;所以直接枚举20…

国产单片机开发汽车气压表胎压计解决方案

一、技术原理 &#xff08;一&#xff09;压力传感技术 压电式压力传感器&#xff1a;利用压电材料的压电效应&#xff0c;当压力作用于压电材料时&#xff0c;会产生与压力成正比的电荷。通过测量电荷的大小&#xff0c;经过转换电路可得到对应的压力值。这种传感器响应速度快…

041集——选取若干点生成三角网(CAD—C#二次开发入门)

随机生成2000个三维点并生成三角网&#xff0c;效果如下&#xff1a; 随机生成20个点&#xff0c;效果如下&#xff1a; 附部分代码如下&#xff1a; public class NTS三角网{public static int numPoints 20;[CommandMethod("xx")]public void 在NTSdemo(){// 获取…

STM32-心知天气项目

一、项目需求 使用 ESP8266 通过 HTTP 获取天气数据&#xff08;心知天气&#xff09;&#xff0c;并显示在 OLED 屏幕上。 按键 1 &#xff1a;循环切换今天 / 明天 / 后天天气数据&#xff1b; 按键 2 &#xff1a;更新天气。 二、项目框图 三、cjson作用 https://gi…

人工智能三剑客:符号主义、连接主义与行为主义的较量与融合

文章目录 1. 符号主义人工智能&#xff1a;逻辑与规则的智慧1.1 核心思想1.2 示例&#xff1a;专家系统配图说明&#xff08;PlantUML&#xff09;&#xff1a; 1.3 存在的问题1.4 训练方法 2. 连接主义人工智能&#xff1a;神经网络的崛起2.1 核心思想2.2 示例&#xff1a;深度…

java如何排查线上问题

在Java线上环境中排查故障需要系统化的方法和合适的工具&#xff0c;以下是详细的排查步骤及常用工具&#xff1a; 快速确认问题现象 明确症状&#xff1a;确认是CPU飙升、内存泄漏、线程阻塞、响应超时&#xff0c;还是频繁Full GC。 查看监控&#xff1a;使用Prometheus、Gr…