学习记录:js算法(七十五): 加油站
文章目录
- 加油站
- 思路一
- 思路二
- 思路三
- 思路四
- 思路五
加油站
在一条环路上有 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 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
思路一
function canCompleteCircuit(gas, cost) {let totalGas = 0, totalCost = 0, start = 0, tank = 0;for (let i = 0; i < gas.length; i++) {totalGas += gas[i];totalCost += cost[i];tank += gas[i] - cost[i];// 如果当前油量小于0,说明从start点出发无法到达下一个加油站if (tank < 0) {start = i + 1; // 更新起始点tank = 0; // 清空油箱}}// 如果总的汽油量小于总的消耗量,无法完成环路if (totalGas < totalCost) {return -1;}return start;
}
讲解
可以通过贪心算法解决,主要的思路是寻找一个起始点,从这个点出发,汽车能够通过不断加油并且不耗尽油箱中的油,完成整个环路的行驶。下面详细介绍解题思路和代码实现。
- 初始化变量:
totalGas
和totalCost
分别用来累计所有加油站的汽油总量和消耗的汽油总量。start
用来记录可能的起始加油站的索引,tank
则记录当前油箱里的油量。- 遍历加油站:从第一个加油站开始遍历,对于每个加油站,做以下操作:
○ 更新油箱里的油量:tank += gas[i] - cost[i]
。
○ 如果油箱里的油量小于**0
,说明从当前的 start 点出发无法到达下一个加油站,因此重置start
点为下一个加油站的位置,并清空油箱:**start = i + 1
和tank = 0
。
○ 累计总汽油量和总消耗量:totalGas += gas[i] 和 totalCost += cost[i]。- 判断能否完成环路:如果
totalGas < totalCost
,说明总的汽油量不足以完成整个环路的行驶,返回-1
。否则,从start
点出发一定可以完成环路,返回start
。
思路二
var canCompleteCircuit = function (gas, cost) {const n = gas.length;for (let start = 0; start < n; start++) {let totalGas = 0;let totalCost = 0;let canComplete = true;for (let i = 0; i < n; i++) {const index = (start + i) % n;totalGas += gas[index];totalCost += cost[index];if (totalGas < totalCost) {canComplete = false;break;}}if (canComplete) {return start;}}return -1;
};
讲解
这段代码定义了一个函数canCompleteCircuit
,用于判断在一个环形路线上,是否可以从某个加油站出发,顺利完成一圈而不耗尽汽油。
- 输入参数:函数接收两个数组
gas
和cost
,分别表示每个加油站的汽油量和从一个加油站到下一个加油站所需的汽油量。- 获取加油站数量:通过
gas.length
获取加油站的数量,并存储在变量n
中。- 外层循环:遍历每一个加油站,尝试将其作为出发点。循环变量
start 从 0 到 n-1
。- 初始化变量:
totalGas
用于记录从当前出发点出发的总汽油量。totalCost
用于记录从当前出发点到下一个加油站的总消耗量。canComplete
标记从当前起点出发是否可以完成一圈,初始设为true
。- 内层循环:从当前起点出发,遍历所有加油站。
循环变量 i 从 0 到 n-1
。
- 计算当前加油站的索引,使用取模运算以实现环形效果。
- 累加汽油量和消耗量:将当前加油站的汽油量加到
totalGas
,将消耗量加到totalCost
。- 检查能否继续行驶:如果
totalGas 小于 totalCost
,说明无法继续行驶,设置canComplete
为false
,并跳出内层循环。- 判断能否完成一圈:如果
canComplete
仍为true
,说明可以从当前起点出发完成一圈,返回当前起点的索引。- 返回结果:如果所有加油站都尝试过后仍然没有找到可以完成一圈的起点,返回
-1
,表示无法完成。
思路三
var canCompleteCircuit = function (gas, cost) {const n = gas.length;const prefix = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + gas[i] - cost[i];}let minPrefix = Infinity;let startIndex = 0;for (let i = 1; i <= n; i++) {if (prefix[i] < minPrefix) {minPrefix = prefix[i];startIndex = i;}}return prefix[n] >= 0 ? (startIndex % n) : -1;
};
讲解
这段代码实现了一个函数canCompleteCircuit
,用于判断在一个环形路线上,是否可以从某个加油站出发,顺利完成一圈而不耗尽汽油。
- 输入参数:函数接收两个数组
gas
和cost
,分别表示每个加油站的汽油量和从一个加油站到下一个加油站所需的汽油量。- 获取加油站数量:通过
gas.length
获取加油站的数量,并存储在变量n
中。- 初始化前缀数组:创建一个长度为
n + 1
的数组prefix
,并用0
填充。这个数组用于存储从起点到每个加油站的净汽油量(汽油量减去消耗量)。- 计算前缀和:
- 使用循环遍历每个加油站,更新
prefix
数组。prefix[i + 1]
存储到达第i
个加油站后的净汽油量。- 计算公式为
prefix[i + 1] = prefix[i] + gas[i] - cost[i]
。- 寻找最小前缀和:
- 初始化
minPrefix
为正无穷,startIndex
为0
。- 再次遍历
prefix
数组,寻找最小的前缀和,并记录其索引startIndex
。- 判断是否可以完成一圈:
- 如果
prefix[n](即完成一圈后的净汽油量)大于等于 0
,说明可以完成一圈,返回startIndex % n
作为起点。- 如果
prefix[n] 小于 0
,返回-1
,表示无法完成。
思路四
var canCompleteCircuit = function (gas, cost) {const n = gas.length;let totalGas = 0;let totalCost = 0;let currentGas = 0;let startIndex = 0;for (let i = 0; i < n; i++) {totalGas += gas[i];totalCost += cost[i];currentGas += gas[i] - cost[i];if (currentGas < 0) {startIndex = i + 1;currentGas = 0;}}return totalGas >= totalCost ? startIndex : -1;
};
讲解
这段代码实现了一个函数canCompleteCircuit
,用于判断在一个环形路线上,是否可以从某个加油站出发,顺利完成一圈而不耗尽汽油。
- 输入参数:
gas
: 一个数组,表示每个加油站的汽油量。cost
: 一个数组,表示从一个加油站到下一个加油站所需的汽油量。- 变量初始化:
n
: 加油站的数量。totalGas
: 用于累加所有加油站的汽油量。totalCost
: 用于累加所有加油站的消耗量。currentGas
: 用于跟踪当前剩余的汽油量。startIndex
: 记录可行的起始加油站索引。- 遍历加油站:
- 使用
for
循环遍历每个加油站。- 在每次迭代中,更新
totalGas
和totalCost
,并计算currentGas
(当前剩余汽油量)。- 判断当前汽油量:
- 如果
currentGas
小于 0,说明从当前startIndex
到第i
个加油站无法完成,更新startIndex
为i + 1
,并重置currentGas
。- 返回结果:
- 在循环结束后,检查
totalGas
是否大于或等于totalCost
。如果是,返回startIndex
,否则返回-1
,表示无法完成一圈。
思路五
var canCompleteCircuit = function (gas, cost) {
const n = gas.length;const dp = new Array(n).fill(0);for (let i = 0; i < n; i++) {dp[i] = gas[i] - cost[i];}let totalGas = 0;let totalCost = 0;let currentGas = 0;let startIndex = 0;for (let i = 0; i < n; i++) {totalGas += gas[i];totalCost += cost[i];currentGas += dp[i];if (currentGas < 0) {startIndex = i + 1;currentGas = 0;}}return totalGas >= totalCost ? startIndex : -1;
};
讲解
这段代码通过使用一个额外的数组dp
来存储每个加油站的净汽油量,并通过一次遍历(时间复杂度 O(n))有效地判断是否存在一个起点,使得从该起点出发能够完成一圈。这种方法同样比暴力法更高效,适用于大规模数据处理。
输入参数:
gas
: 一个数组,表示每个加油站的汽油量。cost
: 一个数组,表示从一个加油站到下一个加油站所需的汽油量。变量初始化:
n
: 加油站的数量。dp
: 一个数组,用于存储每个加油站的净汽油量(gas[i] - cost[i]
)。totalGas
: 用于累加所有加油站的汽油量。totalCost
: 用于累加所有加油站的消耗量。currentGas
: 用于跟踪当前剩余的汽油量。startIndex
: 记录可行的起始加油站索引。计算净汽油量:
- 使用
for
循环遍历每个加油站,将dp[i]
设置为gas[i] - cost[i]
,表示从第i
个加油站出发的净汽油量。遍历加油站:
- 再次使用
for
循环遍历每个加油站。- 在每次迭代中,更新
totalGas
和totalCost
,并计算currentGas
(当前剩余汽油量)。判断当前汽油量:
- 如果
currentGas
小于 0,说明从当前startIndex
到第i
个加油站无法完成,更新startIndex
为i + 1
,并重置currentGas
。返回结果:
- 在循环结束后,检查
totalGas
是否大于或等于totalCost
。如果是,返回startIndex
,否则返回-1
,表示无法完成一圈。
相关文章:

学习记录:js算法(七十五): 加油站
文章目录 加油站思路一思路二思路三思路四思路五 加油站 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发…...

强心剂!EEMD-MPE-KPCA-LSTM、EEMD-MPE-LSTM、EEMD-PE-LSTM故障识别、诊断
强心剂!EEMD-MPE-KPCA-LSTM、EEMD-MPE-LSTM、EEMD-PE-LSTM故障识别、诊断 目录 强心剂!EEMD-MPE-KPCA-LSTM、EEMD-MPE-LSTM、EEMD-PE-LSTM故障识别、诊断效果一览基本介绍程序设计参考资料 效果一览 基本介绍 EEMD-MPE-KPCA-LSTM(集合经验模态分解-多尺…...

yarn的安装与使用以及与npm的区别(安装过程中可能会遇到的问题)
一、yarn的安装 使用npm就可以进行安装 但是需要注意的一点是yarn的使用和node版本是有关系的必须是16.0以上的版本。 输入以下代码就可以实现yarn的安装 npm install -g yarn 再通过版本号的检查来确定,yarn是否安装成功 yarn -v二、遇到的问题 1、问题描述…...

大数据行业预测
大数据行业预测 编译 李升伟 和所有预测一样,我们必须谨慎对待这些预测,因为其中一些预测可能成不了事实。当然,真正改变游戏规则的创新往往出乎意料,甚至让最警惕的预言家也措手不及。所以,如果在来年发生了一些惊天…...

可能是NextJs(使用ssr、api route)打包成桌面端(nextron、electron、tauri)的最佳解决方式
可能是NextJs(使用ssr、api route)打包成桌面端(nextron、electron、tauri)的最佳解决方式 前言 在我使用nextron(nextelectron)写了一个项目后打包发现nextron等一系列桌面端框架在生产环境是不支持next的ssr也就是api route功能的这就导致我非常难受&…...

二百七十、Kettle——ClickHouse中增量导入清洗数据错误表
一、目的 比如原始数据100条,清洗后,90条正确数据在DWD层清洗表,10条错误数据在DWD层清洗数据错误表,所以清洗数据错误表任务一定要放在清洗表任务之后。 更关键的是,Hive中原本的SQL语句,放在ClickHouse…...

CentOS6升级OpenSSH9.2和OpenSSL3
文章目录 1.说明2.下载地址3.升级OpenSSL4.安装telnet 服务4.1.安装 telnet 服务4.2 关闭防火墙4.2.使用 telnet 连接 5.升级OpenSSH5.1.安装相关命令依赖5.2.备份原 ssh 配置5.3.卸载原有的 OpenSSH5.4.安装 OpenSSH5.5.修改 ssh 配置文件5.6关闭 selinux5.7.重启 OpenSSH 1.说…...

2024 年 MathorCup 数学应用挑战赛——大数据竞赛-赛道 A:台风的分类与预测
2024年MathorCup大数据挑战赛-赛道A初赛--思路https://download.csdn.net/download/qq_52590045/89922904↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓…...

kotlin实现viewpager
说明:kotlin tablayout viewpager adapter实现滑动界面 效果图 step1: package com.example.flushfragmentdemoimport androidx.appcompat.app.AppCompatActivity import android.os.Bundle import androidx.fragment.app.Fragment import androidx.viewpager2.adapter.…...

RabbitMQ最新版本4.0.2在Windows下的安装及使用
RabbitMQ 是一个开源的消息代理和队列服务器,提供可靠的消息传递和队列服务。它支持多种消息协议,包括 AMQP、STOMP、MQTT 等。本文将详细介绍如何在 Windows 系统上安装和使用最新版本的 RabbitMQ 4.0.2。 前言 RabbitMQ 是用 Erlang 语言开发的 AMQP&…...

东方博宜1180 - 数字出现次数
问题描述 有 50 个数( 0∼19),求这 50个数中相同数字出现的最多次数为几次? 输入 50 个数字。 输出 1 个数字(即相同数字出现的最多次数)。 样例 输入 1 10 2 0 15 8 12 7 0 3 15 0 15 18 16 7 17 16 9 …...

LeetCode: 3274. 检查棋盘方格颜色是否相同
一、题目 给你两个字符串 coordinate1 和 coordinate2,代表 8 x 8 国际象棋棋盘上的两个方格的坐标。 以下是棋盘的参考图。 如果这两个方格颜色相同,返回 true,否则返回 false。 坐标总是表示有效的棋盘方格。坐标的格式总是先…...

datax编译并测试
mvn -U clean package assembly:assembly -Dmaven.test.skiptrue 参看:DataX导数的坑_datax插件初始化错误, 该问题通常是由于datax安装错误引起,请联系您的运维解决-CSDN博客 两边表结构先创建好: (base) [rootlnpg bin]# pwd /db/DataX-datax_v20230…...

2-133 基于matlab的粒子群算法PSO优化BP神经网络
基于matlab的粒子群算法PSO优化BP神经网络,BP神经网络算法采用梯度下降算法,以输出误差平方最小为目标,采用误差反向传播,训练网络节点权值和偏置值,得到训练模型。BP神经网络的结构(层数、每层节点个数)较复杂时&…...

复盘秋招22场面试(四)形势重新评估与后续措施
连续好多天睡不着觉,经常晚上起来好几次,到现在还是没offer。之前有个校友在抖音留言说我能收到这么多面试说明简历没问题,这么多一面挂,说明我技术面有问题。确实有一些是kpi面,但是我复盘之后我发现也没有那么多kpi面…...

揭开C++ STL的神秘面纱之string:提升编程效率的秘密武器
目录 🚀0.前言 🚈1.string 构造函数 🚝1.1string构造函数 🚝1.2string拷贝构造函数 🚈2.string类的使用 🚝2.1.查询元素个数或空间 返回字符串中有效字符的个数:size lenth 返回字符串目…...

用人工智能,应该怎么掏钱?
人工智能(AI)服务的发展正快速改变企业和开发者的工作方式,不仅提供了强大的数据分析和预测能力,还涵盖了从自然语言处理到图像识别的广泛功能。然而,理解AI服务的支付模式对成本控制和合理资源分配至关重要࿰…...

【Axure高保真原型】移动案例
今天和大家分享多个常用的移动案例的原型模板,包括轮盘滑动控制元件移动、页面按钮控制元件移动、鼠标单击控制元件移动、元件跟随鼠标移动、鼠标拖动控制元件移动、键盘方向键控制元件移动,具体效果可以点击下方视频观看或打开下方预览地址查看哦 【原…...

Bytebase 3.0.0 - AI 助手全面升级
🚀 新功能 SQL 编辑器里的 AI 助手:支持将自然语言转换成 SQL 语句,解释 SQL 代码,还能帮助发现潜在问题。 支持 SQL Server DML 语句一键回滚。支持 MariaDB 的在线大表变更。新的 SQL 审核规则: 要求为 MySQL 设置 …...

php基础:数据类型、常量、字符串
语法补充: 每句必须以;结尾 echo:能输出一个以上的字符串,英文逗号隔开 print:只能输出一个字符串并返回1 1.数据类型 php可以自动识别数据类型。 php有5种数据类型:String(字符串…...

Discuz发布原创AI帖子内容生成:起尔 | AI原创帖子内容生成插件开发定制
Discuz发布原创AI帖子内容生成:起尔 | AI原创帖子内容生成插件开发定制 在当今互联网快速发展的时代,内容创作成为了网站运营、社交媒体管理和个人博客维护不可或缺的一部分。然而,高质量内容的创作往往耗时耗力,特别是对于需要频…...

el-table在某些条件下禁止选中
el-table在某些条件下禁止选中 废话不多说直接上代码 HTML部分 <el-table v-loading"loading" :data"wmsShipmentOrderList" ref"multipleTable" select"handleSelect" selection-change"handleSelectionChange">&…...

深入探讨 HTTP 请求方法:GET、POST、PUT、DELETE 的实用指南
文章目录 引言GET 方法POST 方法PUT 方法DELETE 方法小结适用场景与特点总结最佳实践 在 API 设计中的重要性 引言 HTTP 协议的背景:介绍 HTTP(超文本传输协议)作为互联网的基础协议,自 1991 年发布以来,成为客户端和…...

深度学习:元学习(Meta-Learning)详解
元学习(Meta-Learning)详解 元学习,也称为“学会学习”,是机器学习中的一个重要子领域,旨在开发能够快速适应新任务或环境的模型,即使这些任务的可用数据非常有限。元学习的核心思想是通过经验学习如何学习…...

uniapp展示本地pdf + 自定义标题
概要 本文主要讲述uniapp打包的Android项目如何展示本地的PDF文件,并设置标题 需求分析 1、因为是打包的Android项目展示本地的PDF文件,首先需要拿到这个本地的PDF文件路径 2、如何在uniapp的vue页面中展示PDF,因为没有直接展示PDF文件的…...

国标GB28181设备管理软件EasyGBS国标GB28181-2016平台更换SQLite数据库的步骤
在当今数字化、智能化的时代,视频监控系统已成为各行各业不可或缺的一部分。国标GB28181设备管理软件EasyGBS,作为一款功能强大的国标视频云服务平台,凭借其广泛的应用场景和卓越的性能,在智慧城市、智慧园区、智慧交通、智慧医疗…...

C++基础与实用技巧第三节:内存管理与性能优化
第二章:C基础与实用技巧 第三节:内存管理与性能优化 1. 动态内存的管理策略与技巧 动态内存管理是C编程的核心部分之一,合理管理内存可以极大提高程序的性能和稳定性。在C中,动态内存的分配和释放通常使用new和delete运算符&am…...

【移动应用开发】界面设计(二)实现水果列表页面
续上一篇博客 【移动应用开发】界面设计(一)实现登录页面-CSDN博客 目录 一、采用ViewBinding实现一个RecyclerView 1.1 在app/build.gradle中添加recyclerview依赖,并打开viewBinding (1)在app/build.gradle中添加…...

基于Multisim的四人智力竞赛抢答器设计与仿真
1)设计任务 设计一台可供 4 名选手参加比赛的智力竞赛抢答器。 用数字显示抢答倒计时间,由“9”倒计到“0”时,无人抢答,蜂鸣器连续响 1 秒。选手抢答时,数码显示选手组号,同时蜂鸣器响 1 秒,倒…...

前端学习---(4)js基础-2
事件: 事件的三要素:事件源、事件、事件驱动程序。 事件处理步骤: (1)获取事件源:document.getElementById(“box”); // 类似于Android里面的findViewById (2)绑定事件: 事件源box.事件onclick…...