力扣134-加油站(java题解)

2024-08-30 23:44
文章标签 java 力扣 题解 134 加油站

本文主要是介绍力扣134-加油站(java题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:134. 加油站 - 力扣(LeetCode)

前情提要:

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法:局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优,并且没有反例来反驳的话就可以用贪心来试试。

题目思路:

该题入手,你可能知道,当总容量减去总消耗量大于等于0,那么该路程一定是可以环路行驶一周的,但是怎么确认出发的加油站编号呢?

我们用贪心的思路来想想。

将每个加油站的净增量(gas[i] - cost[i])算出,其实就是从该加油站出发到下一站所得到的油。

我们将每一个加油站的净增量累加,如果该和小与0,说明到该加油站的油量已经不足了,那么只有从下一站才可能为出发点。

举个例子。

在这里插入图片描述

从0到4我们开始累加,我们加到2时发现,我们剩余的油量已经不支持我们到达2了,那0和1就不可能是出发点,我们的出发点只会3后面。

因为不管是从0还是1开始到2的油量都为负数了,所以肯定是不可能从0和1出发的。

那i+1后面就不会出现更大的负数?

如果出现更大的负数,就是更新i,那么起始位置又变成新的i+1了。

那么局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行。全局最优:找到可以跑一圈的起始位置

最终代码:

class Solution {//如果该路线的总消耗量减去总增长量为0 那么一定是可以走完全程的 现在我们就是要确认出发点//本题首先我们要把到每个加油站油的净增量 res[i] = gas[i] - cost[i]给算出来 并累加起来 //如果我们从0到i连续累加小与0 说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。//也就是我们这个连续和的区间不可能行驶一圈了 因为我们的剩油量小于0 不能到达下一个加油站//此时我们只有从下一个加油站开始出发才可能会走完一圈//所以我们的局部最优就是:当前累加的和只要小与0 就会从下一个加油站开始重新出发 //全局最优 找到可以走完一圈的路线public int canCompleteCircuit(int[] gas, int[] cost) {int curSum = 0;//totalSum就是所有加油站加起来的净增量,如果小与0 那么不可能会走完一圈int totalSum = 0;int nextIndex = 0;for(int i = 0;i < gas.length;i++){curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];//当curSum<0时 那前面的 0 到 i都不可能是起始位置 只有后面的才有可能为起始位置//也就是我们在实时更新我们出发的位置 直到可以走完一圈//其实我们的起始位置肯定是前面的连续和为负数 后面的都大于0if(curSum < 0){//在这里我们更新出发点,此时前面加油站所累加的油就要清空nextIndex = i + 1;curSum = 0;}}if(totalSum < 0)return -1;return nextIndex;}
}

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!

这篇关于力扣134-加油站(java题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122274

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一