【LeetCode】134. 加油站 - 贪心算法

这篇具有很好参考价值的文章主要介绍了【LeetCode】134. 加油站 - 贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

134. 加油站

贪心思想: 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件:

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

综上可得:贪心算法就是做出当前状态下的最优选择认为就可以解决问题。

在本题中,要找到一个位置能够绕行一周回来。

“假设从x加油站出发经过z加油站最远能到达y加油站,那么从z加油站直接出发,不可能到达y下一个加油站。因为从x出发到z加油站时肯定 有存储的油 或者 到z的时候油已经没了加上z加油站能够加上的油,这都到不了y的下一站。而直接从z出发刚开始是没有存储的油的,所以更不可能到达y的下一站。”

也就是说,我们首先检查第 0 个加油站,并试图判断能否环绕一周;如果不能,就从第一个无法到达的加油站开始继续检查。文章来源地址https://www.toymoban.com/news/detail-663531.html

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int index = 0;
        // 这里不用for循环是因为,我们会使用跳过一些下标。所以,使用while是最好的
        // 从头到尾遍历每个加油站,并且检查以该加油站为起点,能否行驶一周
        while (index < length) {
            // 当前index加油站的总汽油
            int sumOfGas = 0;
            // 当前index加油站的总花费汽油
            int sumOfCost = 0;
            // 当前index加油站最远能够走的最远步数
            int count = 0;
            // 判断从当前index下标出发能否环形一周
            while (count < length) {
                // 当前index加油站组成环形加油站
                // 环形加油站下标
                int currentIndex = (index + count) % length;
                sumOfCost += cost[currentIndex];
                sumOfGas += gas[currentIndex];
                // 如果这个环形下标站点发现油不够了
                if (sumOfCost > sumOfGas) {
                	// 当前index加油站组成环形加油站肯定是不满足题意的,跳出循环
                    break;
                }
                // 最远的步数+1
                count++;
            }
            // 当前index能够环形一周
            if (count == length) {
                // 返回
                return index;
            } else {
                // 就从无法到达的加油站开始继续检查。
                index = index + count + 1;
            }
        }
        // 所有加油站作为起点都不满足
        return -1;
    }
}

到了这里,关于【LeetCode】134. 加油站 - 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果

    目录 🎈LeetCode1005.K次取反后最大化的数组和  🎈LeetCode134.加油站 🎈LeetCode135.分发糖果 链接:1005.K次取反后最大化的数组和 给你一个整数数组  nums  和一个整数  k  ,按以下方法修改该数组: 选择某个下标  i  并将  nums[i]  替换为  -nums[i]  。 重复这个过程恰好  k  次

    2024年02月16日
    浏览(44)
  • LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)

    参考前文 参考文章: LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和) LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II) LeetCode链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 首先 sor

    2024年02月09日
    浏览(46)
  • Day34 贪心算法 part03 1005. K 次取反后最大化的数组和 134. 加油站 135. 分发糖果

    思路 第一步,从前向后遍历,遇到负数将其变为正数,同时K– 第二步:如果K还大于0,那么反复转变数值最小的元素,将K用完 第三步:求和 方法一(暴力) leetcode超时(35/40) 方法二(贪心)

    2024年01月19日
    浏览(42)
  • 第八章 贪心算法 part03 1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果 (day34补)

    给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组: 选择某个下标 i  并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后,返回数组 可能的最大和 。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -100

    2024年02月11日
    浏览(37)
  • 加油站【贪心算法】

    加油站 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行

    2024年02月11日
    浏览(39)
  • 134. 加油站 Python

    在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组 gas 和 cost ,如果你可以绕环路行驶一周,则返

    2024年02月04日
    浏览(35)
  • DAY38:贪心算法(五)K次取反后最大数组和+加油站

    本题重点是逻辑问题,同时复习static和sort的自定义操作与时间复杂度 给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组: 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后,返回数组 可能的

    2024年02月13日
    浏览(45)
  • 力扣算法刷题Day34|贪心:K次取反后最大化的数组和 加油站 分发糖果

    力扣题目:# 1005.K次取反后最大化的数组和  刷题时长:10min 解题方法:贪心 复杂度分析 时间O(n) 空间O(1) 问题总结 无 本题收获 贪心思路:两次贪心 在包含正负无序的整数数组中,如何转变K次正负,让数组和达到最大 局部最优:让绝对值大的负数变为正数,当前数值达到

    2024年02月09日
    浏览(57)
  • C++力扣题目1005--K次取反后最大化的数组和 134--加油站 135--分发糖果

    力扣题目链接(opens new window) 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。) 以这种方式修改数组后,返回数组可能的最大和。 示例 1: 输入:A = [4,2,3],

    2024年01月21日
    浏览(47)
  • 加油站抽烟烟火智能识别算法

    加油站抽烟烟火智能识别系统通过yolo+opencv网络模型图像识别分析技术,加油站抽烟烟火智能识别算法识别出抽烟和燃放烟火的情况,并发出预警信号以提醒相关人员,减少火灾风险。OpenCV基于C++实现,同时提供python, Ruby, Matlab等语言的接口。OpenCV-Python是OpenCV的Python API,结合

    2024年02月11日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包