当前位置: 首页 > article >正文

面试经典题目:LeetCode134_加油站

leetcode134_加油站

在这里插入图片描述

题目链接:leetcode134_加油站

暴力解法

暴力解法会尝试每个加油站作为起点,模拟一圈行驶来验证是否能成功环绕一周。这种方法的时间复杂度是 O(n^2)(超时),因为它对每个可能的起点都进行了完整的模拟。以下是暴力解法的简化描述:

  1. 遍历所有加油站:将每一个加油站作为潜在的起点。
  2. 模拟行驶:从当前选择的起点开始,检查是否有足够的油量到达下一个加油站,并继续此过程直到回到起点。
  3. 返回结果:如果找到一个成功的起点,则返回该索引;如果所有起点都无法完成一圈,则返回 -1

暴力解法的问题在于它没有利用已经获得的信息,每次都要重新计算,导致了不必要的重复工作。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int len = gas.size();
        for (int index = 0; index < len; index++)
        {
            int i = index, sum = gas[i],end=0;
            bool flag = false;
            while (sum >= cost[i])
            {
                sum = sum - cost[i] + gas[(i + 1) % len];
                end=i+1;
                i = end % len;
                if ((end == len && index == 0) || i == 0)
                    flag = true;
                if (flag && i == index)
                    return index;
            }
        }
        return -1;
    }
};

贪心算法

初始条件

x x x y y y 是两个加油站,且 x < y x < y x<y

  • g a s [ i ] gas[i] gas[i] 表示第 i i i 个加油站的油量。
  • c o s t [ i ] cost[i] cost[i] 表示从第 i i i 个加油站到下一个加油站所需的油量。

第一个不等式

∑ i = x y g a s [ i ] < ∑ i = x y c o s t [ i ] \sum_{i=x}^{y} gas[i] < \sum_{i=x}^{y} cost[i] i=xygas[i]<i=xycost[i]

这个不等式表明从加油站 $ x $ 到加油站 $ y $ 的总油量不足以覆盖这段路程所需的总油量,因此无法直接从 $ x $ 到达 $ y $。

第二个不等式

∑ i = x j g a s [ i ] ≥ ∑ i = x j c o s t [ i ] (对于所有  j ∈ [ x , y ) ) \sum_{i=x}^{j} gas[i] \geq \sum_{i=x}^{j} cost[i] \quad \text{(对于所有 } j \in [x, y)) i=xjgas[i]i=xjcost[i](对于所有 j[x,y))

这个不等式表明对于所有位于 $ x $ 和 $ y $ 之间的加油站 $ j $,从 $ x $ 到 $ j $ 的总油量足以覆盖这段路程所需的总油量,因此可以到达这些加油站。

考虑任意加油站 z z z

现在考虑任意一个位于 x x x y y y 之间的加油站 z z z,我们需要判断从 z z z 出发是否能到达 y y y

推导过程

  1. 分解和

    ∑ i = z y g a s [ i ] = ∑ i = x y g a s [ i ] − ∑ i = x z − 1 g a s [ i ] \sum_{i=z}^{y} gas[i] = \sum_{i=x}^{y} gas[i] - \sum_{i=x}^{z-1} gas[i] i=zygas[i]=i=xygas[i]i=xz1gas[i]

  2. 应用第一个不等式

    ∑ i = x y g a s [ i ] < ∑ i = x y c o s t [ i ] \sum_{i=x}^{y} gas[i] < \sum_{i=x}^{y} cost[i] i=xygas[i]<i=xycost[i]

    因此,

    ∑ i = x y g a s [ i ] − ∑ i = x z − 1 g a s [ i ] < ∑ i = x y c o s t [ i ] − ∑ i = x z − 1 g a s [ i ] \sum_{i=x}^{y} gas[i] - \sum_{i=x}^{z-1} gas[i] < \sum_{i=x}^{y} cost[i] - \sum_{i=x}^{z-1} gas[i] i=xygas[i]i=xz1gas[i]<i=xycost[i]i=xz1gas[i]

  3. 应用第二个不等式

    ∑ i = x z − 1 g a s [ i ] ≥ ∑ i = x z − 1 c o s t [ i ] \sum_{i=x}^{z-1} gas[i] \geq \sum_{i=x}^{z-1} cost[i] i=xz1gas[i]i=xz1cost[i]

    因此,

    ∑ i = x y c o s t [ i ] − ∑ i = x z − 1 g a s [ i ] < ∑ i = x y c o s t [ i ] − ∑ i = x z − 1 c o s t [ i ] \sum_{i=x}^{y} cost[i] - \sum_{i=x}^{z-1} gas[i] < \sum_{i=x}^{y} cost[i] - \sum_{i=x}^{z-1} cost[i] i=xycost[i]i=xz1gas[i]<i=xycost[i]i=xz1cost[i]

  4. 简化表达式

    ∑ i = x y c o s t [ i ] − ∑ i = x z − 1 c o s t [ i ] = ∑ i = z y c o s t [ i ] \sum_{i=x}^{y} cost[i] - \sum_{i=x}^{z-1} cost[i] = \sum_{i=z}^{y} cost[i] i=xycost[i]i=xz1cost[i]=i=zycost[i]

  5. 最终结论

    ∑ i = z y g a s [ i ] < ∑ i = z y c o s t [ i ] \sum_{i=z}^{y} gas[i] < \sum_{i=z}^{y} cost[i] i=zygas[i]<i=zycost[i]

结论

从任意一个位于 x x x y y y 之间的加油站 z z z 出发,都无法到达加油站 y y y,因为从 z z z y y y 的总油量不足以覆盖这段路程所需的总油量。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalTank = 0, currentTank = 0;
        int startingStation = 0;

        for (int i = 0; i < gas.size(); ++i) {
            // 更新总油量和当前油量
            totalTank += gas[i] - cost[i];
            currentTank += gas[i] - cost[i];

            // 如果当前油量为负,说明从起点到当前位置不可能到达,更新起点为下一个位置
            if (currentTank < 0) {
                startingStation = i + 1;
                currentTank = 0; // 重置当前油量
            }
        }

        // 如果总油量为非负数,说明可以完成一圈;否则不能完成
        return totalTank >= 0 ? startingStation : -1;
    }
};

http://www.kler.cn/a/449239.html

相关文章:

  • 运维工程师面试系统监控与优化自动化与脚本云计算的理解虚拟化技术的优点和缺点
  • 学习“Kotlin编程指南”笔记
  • curl也支持断点续传
  • day11|150,239,347
  • Go 1.24即将到来!
  • 浅谈目前我开发的前端项目用到的设计模式
  • 对安全的认知
  • Java 8使用Stream流去除一个list中包含另一个list已存在的某个字段的对象
  • 基于空间状态方程的车辆行驶控制系统simulink建模与仿真,对比前馈控制和PI反馈控制
  • 序列任务中的位置信息编码方法综述:原因、方法及适用场景
  • 前端组件设计:从封装到复用的最佳实践
  • Pytorch | 从零构建EfficientNet对CIFAR10进行分类
  • VLAN之间通讯
  • 用C语言实现线程池
  • 大数据实验三
  • 从0到1搭建 Android 自动化 python+appium 环境
  • MAE 随机掩码自编码器:高掩码率 + 非对称编码器-解码器架构,解决视觉数据冗余特征、计算冗余消除
  • web3跨链预言机协议-BandProtocol
  • 基于java的改良版超级玛丽小游戏
  • Python:基础语法
  • 每日一题(4)
  • R语言中vegan软件包使用教程
  • Zookeeper的选举机制
  • JVM对象分配内存如何保证线程安全?
  • leetcode 2295.替换数组中的元素
  • ElasticSearch 使用教程