贪心算法-加油站

一、题目描述

二、解题思路

1.运动过程分析

        这里需要一个油箱剩余油量的变量resGas,初始化resGas=0;还需要一个标记从什么位置当做初始位置的startIdx,初始化startIdx=0。

        我们从数组下标idx=0处开始向后遍历,初始时startIdx=0,遇到下标为idx的加油站时,看邮箱内此时剩余油量能否到达下一个油站:

        resGas=resGas+gas[i]-cost[i]

        当resGas>=0时,可以到达下一个油站;

        当resGas<0时,不可以到达下一个油站,此时也意味着从startIdx开始运动到达不了idx位置,从startIdx到idx之间的所有位置也同样不可达idx此时把startIdx设置为idx+1。

        这里用startIdx->idx小车运动不可达的图示解释一下上面标注黄色部分:

2.可以循环的条件判断

        这里需要注意的是,小车从startIdx->加油站数组末尾时,如果可达,需要将idx=(idx+1)%gas.length,如果整个过程一直可达,等到二次循环idx+1==startidx时,意味着从startIdx开始行驶一定可以循环一周,返回startIdx。所以我们还要添加一个变量标注一下此时是否已经二次循环,实现代码内用newloop来标识

3.不可以循环的条件判断

        不存在循环一周的情况:当二次循环过程中还是出现了不可达的情况,那么就意味着不存在循环的情况,返回-1,图示:

        就意味着从startIdx到末尾之间的元素和下标0到下标3之间的所有元素下标3都不可达,此前已经确定了从下标0到下标4之间的元素已经不可达,所以肯定不能形成循环。

        整个过程需要执行两次数组遍历,所以时间复杂度为O(n),效率还是可以的。

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param gas int整型一维数组 * @param cost int整型一维数组 * @return int整型*/public int gasStation (int[] gas, int[] cost) {// 就从0开始寻找,设置油箱剩余量resGas,int len=gas.length;int startidx=0,residx=0;int resGas=0;//初始时油箱剩余油量为0int nowidx=0;boolean newloop=false;while(nowidx<len){int nowGas=resGas+gas[nowidx]-cost[nowidx];if(nowidx+1==len){newloop=true;}if(nowGas<0){//表示从startidx开始到达不了startidx=(nowidx+1)%len;resGas=0;if(newloop){residx=-1;break;}}else{//表示当前油量还可以支撑往后走resGas=nowGas;if(newloop&&((nowidx+1)%len==startidx)){residx=startidx;break;}}nowidx=(nowidx+1)%len;}return residx;}
}

四、刷题链接

加油站_牛客题霸_牛客网

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/344855.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

go语言进阶 init() 函数

go 语言包 在一个项目中通常我们需要引入第三方包&#xff0c;我们来看下 当我们导入一个包的时候 发生了什么&#xff1a; 首先我们先详细介绍下两个函数&#xff1a; init(), main() 是 go 语言中的保留函数。我们可以在源码中 定义 init()函数&#xff0c; 此函数会在包导入…

代码随想录——将有序数组转化为二叉搜索树(Leetcode108)

题目链接 递归 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* …

Java Web学习笔记24——Vue项目开发流程

import是引入文件。 export是将对象导出为模块。 new Vue({ router, router: h > h(App) }).$mount(#app) App.vue: vue的组成文件以.vue结尾&#xff0c;每个组件由三个部分组成&#xff1a;<template>、<script>、<style>。 <template><d…

Transformer学习之SwinTransformer

1.算法简介 本文主要参考自以下链接&#xff0c;整理成线上的形式用于备忘&#xff0c;排版太麻烦了直接贴图&#xff0c;参考的朋友慎重&#xff0c;不如直接看参考链接&#xff0c;后期有了新的理解继续更正。 参考链接1&#xff1a;Swin-Transformer网络结构详解_swin tran…

基于JSP技术的文物管理系统

你好呀&#xff0c;我是计算机学长猫哥&#xff01;如果有相关需求&#xff0c;文末可以找到我的联系方式。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;JSP技术 工具&#xff1a;IDEA/Eclipse、Navicat、Maven 系统展示 首页 管理员界面 用户前台…

mysql (事物)

一.什么是事物 事物是一组操作的集合&#xff0c;不可分割的工作单位&#xff0c;事物会把所有的操作当作一个整体一起向系统提交或撤销操作请求&#xff0c;就是这些操作要么一起成功要么一起失败。 二.事物操作 &#xff08;这个就是一个理解&#xff09; 1.事务特性 原子性…

【虚拟现实】二、主要的AR/VR硬件设备

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 2.1 微软HoloLens 微软HoloLens是一款领先的混合现实设备&#xff0c;结合了AR和VR的元素&#xff0c;允许用户…

ssm601基于ssm框架的校园闲置物品交易平台+jsp【已测试】

前言&#xff1a;&#x1f469;‍&#x1f4bb; 计算机行业的同仁们&#xff0c;大家好&#xff01;作为专注于Java领域多年的开发者&#xff0c;我非常理解实践案例的重要性。以下是一些我认为有助于提升你们技能的资源&#xff1a; &#x1f469;‍&#x1f4bb; SpringBoot…

lua vm 五: upvalue

前言 在 lua vm 中&#xff0c;upvalue 是一个重要的数据结构。upvalue 以一种高效的方式实现了词法作用域&#xff0c;使得函数能成为 lua 中的第一类值&#xff0c;也因其高效的设计&#xff0c;导致在实现上有点复杂。 函数 (proto) upvalue 构成了闭包&#xff08;closu…

【C++ STL】模拟实现 string

标题&#xff1a;【C :: STL】手撕 STL _string 水墨不写bug &#xff08;图片来源于网络&#xff09; C标准模板库&#xff08;STL&#xff09;中的string是一个可变长的字符序列&#xff0c;它提供了一系列操作字符串的方法和功能。 本篇文章&#xff0c;我们将模拟实现STL的…

数据结构---树与二叉树

个人介绍 hello hello~ &#xff0c;这里是 code袁~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的…

【中国开源生态再添一员】天工AI开源自家的Skywork

刚刚看到《AI高考作文出圈&#xff0c;网友票选天工AI居首》&#xff0c;没想到在Huggingface中发现了Skywork大模型。天工大模型由昆仑万维自研&#xff0c;是国内首个对标ChatGPT的双千亿级大语言模型&#xff0c;天工大模型通过自然语言与用户进行问答式交互&#xff0c;AI生…

Linux系统管理:虚拟机Almalinux 9.4 安装

目录 一、理论 1.Almalinux 二、实验 1.虚拟机Almalinux 9.4 安装准备阶段 2.安装Almalinux 9.4 3.Termius远程连接 一、理论 1.Almalinux (1) 简介 Almalinux是一个开源、社区拥有和管理、免费的企业Linux发行版。专注于长期稳定性&#xff0c;并提供强大的生产级…

机器学习--损失函数

损失函数&#xff08;Loss Function&#xff09;&#xff0c;也称为代价函数&#xff08;Cost Function&#xff09;或误差函数&#xff08;Error Function&#xff09;&#xff0c;是机器学习和统计学中的一个重要概念。它用于量化模型预测值与真实值之间的差异。损失函数的值…

Python一些小操作

矢量图 from matplotlib_inline import backend_inline backend_inline.set_matplotlib_formats(svg)matplotlib中文问题 import matplotlib.pyplot as plt plt.rcParams["font.sans-serif"]["SimHei"] #设置字体 plt.rcParams["axes.unicode_minus…

docker部署redis实践

1.拉取redis镜像 # 拉取镜像 sudo docker pull redis2.创建映射持久化目录 # 创建目录 sudo mkdir -p $PWD/redis/{conf,data}3. 运行redis 容器&#xff0c;查看当前redis 版本号 # 运行 sudo docker run --name redis -d -p 6379:6379 redis # 查看版本号 sudo docker ex…

力扣每日一题129:从根节点到叶子节点的和

题目 中等 相关标签 相关企业 给你一个二叉树的根节点 root &#xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字&#xff1a; 例如&#xff0c;从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节…

【Java】单例设计模式

单例设计模式简介 目录 1.单例设计模式是什么&#xff1f;2.单例设计模式设计方法饿汉式懒汉式 3.单例设计模式的应用任务管理器(仅有一个页面&#xff0c;不可多开)Runtime运行环境 1.单例设计模式是什么&#xff1f; 设计模式 是解决 特定问题的优秀设计方式之一。 单例设计…

基于springboot的教学管理系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;教师管理&#xff0c;学生管理&#xff0c;课程管理 教师账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;课程管理&#xff0c;课程表信…

LibreOffice电子表格如何实现快速筛选并将结果放到新的工作表

如果是在excel或者wps中&#xff0c;可能大家都习惯了自动筛选&#xff0c;然后复制到新的工作表或者删除掉复制内容的办法。但是在LibreOffice中&#xff0c;经测试&#xff0c;大数据表的删除或者复制是非常慢的。这也是很多人放弃LibreOffice的原因之一。那么我们如何快速筛…