134.加油站

LeetCode LeetCode 数组 动态规划
发布时间 :
字数:3.9k 阅读 : 评论:
  1. 134.加油站
    1. 134.1 题目
    2. 134.2 题解
      1. 暴力法
      2. 贪心算法
      3. 递归
    3. 134.3 代码
    4. 134.4 运行结果

134.加油站

134.1 题目

在一条环路上有 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

134.2 题解

暴力法

// 方法一：暴力法
// 初始化起始索引为 0
// 循环遍历每个加油站作为起点
// 在每个起点尝试行驶一圈，即从当前加油站出发，尝试到达下一个加油站
// 在每次尝试行驶一圈时，初始化当前加油站到达下一站时的汽油总量和花费总量
// 在循环中，依次计算当前加油站到达下一站时的汽油总量和花费总量
// 如果发现花费大于汽油总量，则表示无法继续行驶，跳出内层循环
// 如果成功行驶一圈，则返回起始索引
// 否则，更新起始索引，以跳过无法行驶的加油站
// 重复以上步骤，直到所有加油站都被尝试过
// 若无法行驶一圈，则返回 -1
static int CanCompleteCircuit1(int[] gas, int[] cost)
{
    // 初始化起始索引为 0
    int index = 0;

    // 循环遍历每个加油站作为起点
    while (index < gas.Length)
    {
        // 初始化当前加油站到达下一站时的汽油总量和花费总量
        int sumGas = 0;
        int sumCost = 0;

        // 初始化当前步数为 0
        int nowStep = 0;

        // 在当前起点开始尝试行驶一圈
        while (nowStep < gas.Length)
        {
            // 计算当前加油站的索引位置
            int nowIndex = (index + nowStep) % gas.Length;

            // 统计当前加油站到达下一站时的汽油总量和花费总量
            sumGas += gas[nowIndex];
            sumCost += cost[nowIndex];

            // 如果花费大于汽油总量，则表示无法继续行驶，跳出内层循环
            if (sumCost > sumGas)
                break;

            // 增加步数
            ++nowStep;
        }

        // 如果成功行驶一圈，返回起始索引
        if (nowStep == gas.Length)
        {
            return index;
        }
        else
        {
            // 否则，更新起始索引，以跳过无法行驶的加油站

            // 为什么要更新到index + nowStep + 1
            // 从 index 到 index + nowStep 的过程中，已经消耗了比获得的汽油更多的油量，导致无法继续前进。因此，尝试从 index + 1 到 index + nowStep 这些加油站作为起点，也是不可行的。
            // 比如index能到index+1 说明此时油量大于等于0 油量更多都到不了index + nowStep 那么以index+1作为起点 油量一开始就为0 肯定也到不了index + nowStep

            // 可以理解为，能跑到下一个加油站的话，说明当前油是大于等于0的
            // 但是发现不能跑到下一加油站，说明到下一加油站耗的油太多
            // 到当前加油站之前的油+当前加油站<到下一加油站耗的油
            // 那么 当前加油站<到下一加油站耗的油
            // 所以不可能从此加油站出发
            index = index + nowStep + 1;
        }
    }

    // 若无法行驶一圈，则返回 -1
    return -1;
}

贪心算法

// 方法二：贪心算法
// 思路：
// 核心逻辑：如果总油量大于或等于总的消耗量，则一定存在一个可行的起点。
// 初始化总汽油量、总花费、油箱剩余量、起始索引
// 遍历加油站数组
// 累加总汽油量和总花费
// 更新油箱剩余量，gas[i] - cost[i] 表示从当前加油站到下一站之间的剩余汽油量
// 如果油箱剩余量小于 0，表示无法到达下一站
// 更新起始索引为下一个加油站
// 重置油箱剩余量为 0
// 如果总汽油量大于等于总花费，则存在解，返回起始索引；否则返回 -1
static int CanCompleteCircuit2(int[] gas, int[] cost)
{
    // 初始化总汽油量、总花费、油箱剩余量、起始索引
    int sumGas = 0;
    int sumCost = 0;
    int tankRemain = 0;
    int start = 0;

    // 遍历加油站数组
    for (int i = 0; i < gas.Length; i++)
    {
        // 累加总汽油量和总花费
        sumGas += gas[i];
        sumCost += cost[i];

        // 更新油箱剩余量，gas[i] - cost[i] 表示从当前加油站到下一站之间的剩余汽油量
        tankRemain += gas[i] - cost[i];

        // 如果油箱剩余量小于 0，表示无法到达下一站
        if (tankRemain < 0)
        {
            // 更新起始索引为下一个加油站
            start = i + 1;
            // 重置油箱剩余量为 0
            tankRemain = 0;
        }
    }

    // 如果总汽油量大于等于总花费，则存在解，返回起始索引；否则返回 -1
    return sumGas >= sumCost ? start : -1;
}

递归

// 方法三：递归
// 使用递归方式判断是否能够绕环一圈，效率较低，不推荐使用
static int CanCompleteCircuit3(int[] gas, int[] cost)
{
    // 遍历每个加油站作为可能的起点
    for (int i = 0; i < gas.Length; i++)
    {
        // 调用递归函数判断从当前加油站出发是否能绕环一圈
        bool canCompleteCircuit = CanCompleteCircuitOneJudge(gas, cost, i, i, 0, true);

        // 如果能绕环一圈，则返回当前起点的索引
        if (canCompleteCircuit)
        {
            return i;
        }
    }

    // 如果遍历完所有加油站仍然没有找到可行的起点，则返回 -1
    return -1;
}

// 递归函数，判断从指定起点出发是否能绕环一圈
static bool CanCompleteCircuitOneJudge(int[] gas, int[] cost, int beginIndex, int nowIndex, int nowGas,
    bool isBegin = false)
{
    // 如果回到了起始加油站（不是第一次回到起始站），则表示能够绕环一圈
    if (beginIndex == nowIndex && !isBegin) return true;

    // 如果当前油箱剩余量加上当前加油站的汽油量小于当前加油站的花费，则无法到达下一站
    if (nowGas + gas[nowIndex] < cost[nowIndex]) return false;

    // 更新当前油箱剩余量和当前加油站索引
    nowGas = nowGas + gas[nowIndex] - cost[nowIndex];
    nowIndex = ++nowIndex % gas.Length;

    // 递归调用，继续判断下一站
    return CanCompleteCircuitOneJudge(gas, cost, beginIndex, nowIndex, nowGas);
}

134.3 代码

using System;

class Solution
{
    static void Main()
    {
        #region 题目

        // 在一条环路上有 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 升汽油。
        // 因此，无论怎样，你都不可能绕环路行驶一周。

        #endregion

        #region 测试

        // 示例 1 测试
        int[] gas1 = { 1, 2, 3, 4, 5 };
        int[] cost1 = { 3, 4, 5, 1, 2 };
        Console.WriteLine($"示例1 方法1 输出：{CanCompleteCircuit3(gas1, cost1)}");
        Console.WriteLine($"示例1 方法2 输出：{CanCompleteCircuit2(gas1, cost1)}");

        // 示例 2 测试
        int[] gas2 = { 2, 3, 4 };
        int[] cost2 = { 3, 4, 3 };
        Console.WriteLine($"示例2 方法1 输出：{CanCompleteCircuit1(gas2, cost2)}");
        Console.WriteLine($"示例2 方法2 输出：{CanCompleteCircuit2(gas2, cost2)}");

        #endregion
    }

    #region 答案

    // 方法一：暴力法
    // 初始化起始索引为 0
    // 循环遍历每个加油站作为起点
    // 在每个起点尝试行驶一圈，即从当前加油站出发，尝试到达下一个加油站
    // 在每次尝试行驶一圈时，初始化当前加油站到达下一站时的汽油总量和花费总量
    // 在循环中，依次计算当前加油站到达下一站时的汽油总量和花费总量
    // 如果发现花费大于汽油总量，则表示无法继续行驶，跳出内层循环
    // 如果成功行驶一圈，则返回起始索引
    // 否则，更新起始索引，以跳过无法行驶的加油站
    // 重复以上步骤，直到所有加油站都被尝试过
    // 若无法行驶一圈，则返回 -1
    static int CanCompleteCircuit1(int[] gas, int[] cost)
    {
        // 初始化起始索引为 0
        int index = 0;

        // 循环遍历每个加油站作为起点
        while (index < gas.Length)
        {
            // 初始化当前加油站到达下一站时的汽油总量和花费总量
            int sumGas = 0;
            int sumCost = 0;

            // 初始化当前步数为 0
            int nowStep = 0;

            // 在当前起点开始尝试行驶一圈
            while (nowStep < gas.Length)
            {
                // 计算当前加油站的索引位置
                int nowIndex = (index + nowStep) % gas.Length;

                // 统计当前加油站到达下一站时的汽油总量和花费总量
                sumGas += gas[nowIndex];
                sumCost += cost[nowIndex];

                // 如果花费大于汽油总量，则表示无法继续行驶，跳出内层循环
                if (sumCost > sumGas)
                    break;

                // 增加步数
                ++nowStep;
            }

            // 如果成功行驶一圈，返回起始索引
            if (nowStep == gas.Length)
            {
                return index;
            }
            else
            {
                // 否则，更新起始索引，以跳过无法行驶的加油站

                // 为什么要更新到index + nowStep + 1
                // 从 index 到 index + nowStep 的过程中，已经消耗了比获得的汽油更多的油量，导致无法继续前进。因此，尝试从 index + 1 到 index + nowStep 这些加油站作为起点，也是不可行的。
                // 比如index能到index+1 说明此时油量大于等于0 油量更多都到不了index + nowStep 那么以index+1作为起点 油量一开始就为0 肯定也到不了index + nowStep

                // 可以理解为，能跑到下一个加油站的话，说明当前油是大于等于0的
                // 但是发现不能跑到下一加油站，说明到下一加油站耗的油太多
                // 到当前加油站之前的油+当前加油站<到下一加油站耗的油
                // 那么 当前加油站<到下一加油站耗的油
                // 所以不可能从此加油站出发
                index = index + nowStep + 1;
            }
        }

        // 若无法行驶一圈，则返回 -1
        return -1;
    }


    // 方法二：贪心算法
    // 思路：
    // 核心逻辑：如果总油量大于或等于总的消耗量，则一定存在一个可行的起点。
    // 初始化总汽油量、总花费、油箱剩余量、起始索引
    // 遍历加油站数组
    // 累加总汽油量和总花费
    // 更新油箱剩余量，gas[i] - cost[i] 表示从当前加油站到下一站之间的剩余汽油量
    // 如果油箱剩余量小于 0，表示无法到达下一站
    // 更新起始索引为下一个加油站
    // 重置油箱剩余量为 0
    // 如果总汽油量大于等于总花费，则存在解，返回起始索引；否则返回 -1
    static int CanCompleteCircuit2(int[] gas, int[] cost)
    {
        // 初始化总汽油量、总花费、油箱剩余量、起始索引
        int sumGas = 0;
        int sumCost = 0;
        int tankRemain = 0;
        int start = 0;

        // 遍历加油站数组
        for (int i = 0; i < gas.Length; i++)
        {
            // 累加总汽油量和总花费
            sumGas += gas[i];
            sumCost += cost[i];

            // 更新油箱剩余量，gas[i] - cost[i] 表示从当前加油站到下一站之间的剩余汽油量
            tankRemain += gas[i] - cost[i];

            // 如果油箱剩余量小于 0，表示无法到达下一站
            if (tankRemain < 0)
            {
                // 更新起始索引为下一个加油站
                start = i + 1;
                // 重置油箱剩余量为 0
                tankRemain = 0;
            }
        }

        // 如果总汽油量大于等于总花费，则存在解，返回起始索引；否则返回 -1
        return sumGas >= sumCost ? start : -1;
    }

    // 方法三：递归
    // 使用递归方式判断是否能够绕环一圈，效率较低，不推荐使用
    static int CanCompleteCircuit3(int[] gas, int[] cost)
    {
        // 遍历每个加油站作为可能的起点
        for (int i = 0; i < gas.Length; i++)
        {
            // 调用递归函数判断从当前加油站出发是否能绕环一圈
            bool canCompleteCircuit = CanCompleteCircuitOneJudge(gas, cost, i, i, 0, true);

            // 如果能绕环一圈，则返回当前起点的索引
            if (canCompleteCircuit)
            {
                return i;
            }
        }

        // 如果遍历完所有加油站仍然没有找到可行的起点，则返回 -1
        return -1;
    }

    // 递归函数，判断从指定起点出发是否能绕环一圈
    static bool CanCompleteCircuitOneJudge(int[] gas, int[] cost, int beginIndex, int nowIndex, int nowGas,
        bool isBegin = false)
    {
        // 如果回到了起始加油站（不是第一次回到起始站），则表示能够绕环一圈
        if (beginIndex == nowIndex && !isBegin) return true;

        // 如果当前油箱剩余量加上当前加油站的汽油量小于当前加油站的花费，则无法到达下一站
        if (nowGas + gas[nowIndex] < cost[nowIndex]) return false;

        // 更新当前油箱剩余量和当前加油站索引
        nowGas = nowGas + gas[nowIndex] - cost[nowIndex];
        nowIndex = ++nowIndex % gas.Length;

        // 递归调用，继续判断下一站
        return CanCompleteCircuitOneJudge(gas, cost, beginIndex, nowIndex, nowGas);
    }

    #endregion
}

134.4 运行结果

示例1 方法1 输出：3
示例1 方法2 输出：3
示例2 方法1 输出：-1
示例2 方法2 输出：-1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏