加油站-(贪心算法)
题目描述
在一条环路上有 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 可为起始索引。
思路分析
首先,我们要判断一个加油站是否能到下一个加油站,需要看gas[j]>cost[j],所以我们关注的点应该是gas[j]-cost[j]。所以我们先计算出经过每个站点,油箱是增加油量还是减少油量。remainder[j]=gas[j]-cost[j]。
然后我们判断,什么时候汽车无法绕一圈呢,也就是汽油不够呢。简单举几个例子就知道,只有在remainder[j]的总和是负数的时候才会出现。比如说remianer=[3,-1,0,-1,0],总和是1,即使大部分是0或者是负数,但还是能找到个起点,然后绕一圈。
最后的重点就是,找出这唯一的起点(题目中说解唯一)。
思路一:联想 最大子数组和
一开始我想到了一个类似的题目:最大子数组和,可以用到贪心、前缀和或者动态规划三种思路解决。但是这个题目求的是最大子数组和,但是本题求的是索引。改写起来的复杂度为O(2N)。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:column = len(gas)remainder = [0] * columnfor i in range(column): #计算经过每个加油站油箱的增量remainder[i] = gas[i] - cost[i]if sum(remainder) < 0:return -1max_value = 0result = 0index = 0max_index = 0flag = True#这里是2*column,因为要考虑是环路,也就是循环数组for i in range(2*column):if flag: #是否要记录当前起始下标index = i%columnflag = Falseresult += remainder[i%column]if result < 0: #从当前下标无法绕一圈result = 0# 再次开始记录下标flag = Trueif result > max_value: #记录这个可能的索引max_value = resultmax_index = indexreturn max_index
思路二:贪心算法
看到leetcode官方解,只需遍历一遍即可找出起始下标。所以对上面的代码修改,如果当前从第index个加油站出发,到第right个加油站时油箱为负数时,那么即使从index-right之间的任意加油站出发,同样无法绕过第right个加油站。比如说你选了第x个加油站(index<x<right),其实从index到x之间油箱剩余的油量肯定是大于等于0的,不然不可能到达第x个加油站。所以从index都到不了right,更别说中间的其他加油站出发了。
所以当遇到油量为负数时,我们直接可以跳过起始和末尾这些加油站,从right+1的加油站开始重新遍历结算。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:column = len(gas)remainder = [0] * columnfor i in range(column):remainder[i] = gas[i] - cost[i]if sum(remainder) < 0:return -1# 如果总和不为负数,那么一定可以找到从一个点开始,能遍历全部qianzhui = 0index = 0while index < column:for j in range(index, column):qianzhui += remainder[j]if qianzhui < 0: # 汽油不够了qianzhui = 0index = j+1breakelse:return index
相关文章:
加油站-(贪心算法)
题目描述 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组 gas…...
k8s-持久化存储PV与PVC(1)
1、概述 为什么 kubernetes 要持久化存储? 在 kubernetes 中部署应用都是以 Pod 的容器运行的,而 Pod 是有生命周期,一旦 Pod 被删除或重启后,这些数据也会随着丢失,则需要对这些数据进行持久化存储。 PV࿱…...
Linux Red Hat Enterprise
下载 https://developers.redhat.com/products/rhel/download 安装...
《中型 Vue 项目:挑战与成长》
一、引言 在当今的前端开发领域,Vue 作为一款渐进式 JavaScript 框架,以其强大的功能和灵活性备受开发者青睐。对于中型 Vue 项目而言,其重要性不言而喻。中型 Vue 项目通常在功能复杂度和规模上介于小型项目和大型项目之间,既需要…...
配置 DNS over HTTPS阻止DNS污染
概念介绍 DOH简介 DNS(域名系统)的主要功能是将域名解析成IP地址,域名的解析工作由DNS服务器完成。从安全角度来看,域名解析的请求传输时通常不进行任何加密,这导致第三方能够很容易拦截用户的DNS,将用…...
Facebook广告文案流量秘诀
Facebook 广告文案是制作有效 Facebook 广告的关键方面。它侧重于伴随广告视觉元素的文本内容。今天我们的博客将深入探讨成功的 Facebook 广告文案的秘密! 一、广告文案怎么写? 正文:这是帖子的正文,出现在您姓名的正下方。它可…...
22. 五子棋小游戏
文章目录 概要整体架构流程技术名词解释技术细节小结 1. 概要 🔊 JackQiao 对 米粒 说:“今天咱们玩个五子棋小游戏,电脑与你轮流在一个 nn 的网格上放置棋子(X 或 O),网格由你输入的正整数n决定࿰…...
fastadmin框架同时使用 阿里云oss和阿里云点播
背景 项目的实际需求中既要用到阿里云oss产品又用到阿里云点播系统,实现完美的统一。设置两个地址downUrl,thirdCode。分别代表阿里云oss上传路径和阿里云点播系统vId。 实现 默认框架你已经集成好阿里云oss集成工作,前端html页面实现 <…...
Java-JMX 组件架构即详解
JMX架构由三个主要组件构成: MBeans(Managed Beans):代表可管理的资源,是JMX的核心。MBean可以是Java类或接口,提供了管理操作的接口,如获取系统信息、设置参数等。MBeanServer&#x…...
unity打包web,发送post请求,获取地址栏参数,解决TypeError:s.replaceAll is not a function
发送post请求 public string url "http://XXXXXXXXX";// 请求数据public string postData "{\"user_id\": 1}";// Start is called before the first frame updatevoid Start(){// Post();StartCoroutine(PostRequestCoroutine(url, postData…...
java+ssm+mysql校园物品租赁网
项目介绍: 使用javassmmysql开发的校园物品租赁网,系统包含管理员、用户角色,功能如下: 管理员:用户管理;物品管理(物品种类、物品信息、评论信息);订单管理࿱…...
Spring Boot中实现JPA多数据源配置指南
本文还有配套的精品资源,点击获取 简介:本文详细介绍了在Spring Boot项目中配置和使用JPA进行多数据源管理的步骤。从引入依赖开始,到配置数据源、创建DataSource bean、定义实体和Repository,最后到配置事务管理器和使用多数据…...
服务器加固
1.服务器密码复杂度 密码最小长度,密码复杂度策略 vim /etc/pam.d/system-auth --------------- #密码配置 #ucredit:大写字母个数;lcredit:小写字母个数;dcredit:数字个数;ocredit:…...
探索CSS中的背景图片属性,让你的网页更加美观
导语:在网页设计中,背景图片的运用能够丰富页面视觉效果,提升用户体验。本文将详细介绍CSS中背景图片的相关属性,帮助大家更好地掌握这一技能。 一、背景图片基本属性 1、background-image 该属性用于设置元素的背景图片。语法如…...
Oracle的打开游标(OPEN_CURSORS)
一、OPEN_CURSORS 概述 OPEN_CURSORS 指定会话一次可以拥有的打开游标(私有 SQL 区域的句柄)的最大数量。可以使用此参数来防止会话打开过多的游标。 OPEN_CURSORS参数说明 特性 描述 参数类型 Integer 默认值 50 修改方式 ALTER SYSTEM PDB级别…...
数值分析—数值积分
研究背景 积分的数学解法为牛顿莱布尼兹公式,数学表示为 ∫ a b f ( x ) d x F ( b ) − F ( a ) \int_{a}^{b} f(x)dxF(b)-F(a) ∫abf(x)dxF(b)−F(a),但应用该方法有如下困难: 1, f ( x ) f(x) f(x)的原函数有时不能用初等函…...
克服大规模语言模型限制,构建新的应用方法——LangChain
大模型 大模型的出现和落地开启了人工智能(AI)新一轮的信息技术革命,改变了人们的生 活方式、工作方式和思维方式。大模型的落地需要数据、算力和算法三大要素。经过几 年发展,大模型的数据集(包括多模态数据集)制作已经形成了规约,Meta、Go…...
计算机网络 —— HTTPS 协议
前一篇文章:计算机网络 —— HTTP 协议(详解)-CSDN博客 目录 前言 一、HTTPS 协议简介 二、HTTPS 工作过程 1.对称加密 2.非对称加密 3.中间人攻击 4.引入证书 三、HTTPS 常见问题 1.中间人能否篡改证书? 2.中间人能否调…...
React第十七章(useRef)
useRef 当你在React中需要处理DOM元素或需要在组件渲染之间保持持久性数据时,便可以使用useRef。 import { useRef } from react; const refValue useRef(initialValue) refValue.current // 访问ref的值 类似于vue的ref,Vue的ref是.value,其次就是vu…...
React第十五节useReducer使用详解差异
useReducer() 的用法注意事项 1、 概述: useReducer() 常用于管理复杂的状态更新逻辑,特别是在状态更新依赖于多个条件或动作时,useReducer 提供了一种更加结构化和可维护的方式来处理状态。可以将更新函数写在组件外面 它与 useState() 相…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
