滑动窗口练习(三)— 加油站问题
题目
测试链接
在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。
解释一下这道题,如下图所示:
路程数组gas和油耗数组cost,假设从A点出发,走到B点路程为1,消耗油量为2,1 - 2 = -1,油量不够支撑走到B点,所以如果从A点出发,无法完整的绕完一圈,B、C、D同理,这道题就是看从哪个出发点出发后,可以顺利的绕完一圈(gas和cost等长)。

滑动窗口
首先,先将给定的 gas[] 和 cost[] 稍稍加工一下,一次遍历,用gas[i] - cost[i],得到的新数组中包含正负数,就是从每个点出发的路程和油耗的差值,看是否有能力到达下一个目的地。
此时如果用暴力方法解这道题的话,只需要从0 ~ N - 1每个位置循环遍历,遍历N个位置。看过程中是否出现负数,如果是负数,则说明不能完成循环,如果不是,结果 >= 0,则证明可以完成循环。
我们这里直接说用滑动窗口的解题思路:
依然是先加工gas[] 和 cost[],不同的是,我们要根据加工出来的gas[] - cost[],搞出来一个2倍gas[]长度的前缀和数组。
因为我们要看从 0 ~ N - 1位置中每个的出发点能否成功绕回来, gas[] - cost[] 加工出来的数组就是从每个点出发能否成功到达下一目的地的数组,所以当累加到N - 1位置时,下一步重新在加上 0 位置的值,来构造出这个2倍长度累加和数组。
这样的做的目的是,我下图中 double.length中下标4的位置,可以看做是从B点出发,又重新绕回A的0位置,下标5的位置,可以看做是从C点出发,重新绕回B点的1位置。一个数组全部可以搞定。
所有原始数组中出发的位置,在double.length中都可以将原始数组的累加和数组加工出来。

怎么加工?
假设我从D点出发,那么在gas - cost中求出来的累加和数组就是{3,2,2,4}(因为要重新往A点加绕回来),对应在double.length中就是划线部分,怎么得出来的呢?
划线数组中的每一个数,都减去划线部分的前一个数(1)。

所以,综上所述,此时我们维护一个窗口最小值,窗口范围就是gos.length,每次窗口变化后,根据窗口内最小值 - 前一个值,如果此时已然 < 0,则说明该位置不是最佳出发点。否则就认为是最佳出发点。
代码
public static int canCompleteCircuit(int[] gas, int[] cost) {boolean[] booleans = goodArray(gas, cost);for (int i = 0; i < booleans.length; i++) {if (booleans[i]) {return i;}}return -1;}public static boolean[] goodArray(int[] gas, int[] cost) {int N = gas.length;int M = N << 1;int[] arr = new int[M];for (int i = 0; i < N; i++) {arr[i] = gas[i] - cost[i];arr[N + i] = gas[i] - cost[i];}for (int j = 1; j < M; j++) {arr[j] += arr[j - 1];}LinkedList<Integer> w = new LinkedList<>();for (int i = 0; i < N; i++) {while (!w.isEmpty() && arr[w.peekLast()] >= arr[i]) {w.pollLast();}w.addLast(i);}boolean[] ans = new boolean[N];for (int offset = 0, i = 0, j = N; j < M; offset = arr[i++], j++) {if (arr[w.peekFirst()] - offset >= 0) {ans[i] = true;}if (w.peekFirst() == i) {w.pollFirst();}while (!w.isEmpty() && arr[w.peekLast()] >= arr[j]) {w.pollLast();}w.addLast(j);}return ans;}
相关文章:
滑动窗口练习(三)— 加油站问题
题目 测试链接 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组…...
udemy angular decoration 自存
番外 为什么一个ts文件变成了component,因为它使用了components装饰器 components is just a class,you export it so angular know how to use it 举例:组件装饰器 decoration前总是有一个符号 decoration的作用(之一?) NgModu…...
msvcr90.dll丢失的解决方法分享,5个快速修复dll文件丢失教程
在今天的电脑使用过程中,我们可能会遇到各种各样的问题。其中之一就是msvcr90.dll丢失的问题。那么,msvcr90.dll是什么?msvcr90.dll丢失对电脑有什么影响?又该如何解决这个问题呢?接下来,我将为大家详细介绍…...
海外媒体发稿:软文发稿推广技巧解析超级实用-华媒舍
随着互联网时代的发展,软文发稿成为推广产品与服务的重要手段之一。本文将向大家介绍软文发稿推广的技巧,帮助您更好地利用软文推广商业活动。无论是拥有自己的品牌还是个人创业者,都可以从中受益。 1. 什么是软文? 软文是指以文…...
vm net 方式 静态ip配置访问主机IP和外网
1、win 11 安装vm,镜像文件 F:\software\VMwork\CentOS-7-x86_64-Everything-1804.iso 2、配置网络 net 方式 3、右击网络--》属性---》更改适配器设置--》vmnet8 属性、这里不做配置会出现主机ping通访问不通的情况,(访问不通,…...
Vue笔记(二)基本语法
基本语法 <style> table {border-collapse: collapse;margin:0 auto; } strong {color: rgb(235, 51, 100); }td, th {padding-left: 6px; } table tr td:first-child {width:150px } table tr td:nth-child(2) {width:300px } </style> <template><tabl…...
前端面试提问(4)
1、手撕防抖与节流、树与对象的转换、递归调用,链表头插法 1.1、防抖 防抖函数用于延迟执行某个函数,直到过了一定的间隔时间(例如等待用户停止输入)后再执行。 即后一次点击事件发生时间距离一次点击事件至少间隔一定时间。 …...
基于BEV+Transformer的地面要素感知+建模技术在高德的应用
导读 本文将主要介绍BEVTransformer端到端感知与建模技术在高德各项业务中的应用,如高精地图中地面要素(包含线要素和地面标识)自动化上的具体方案及其演化过程。该方案使用BEVTransformer技术来实现采集车上不同传感器(包含激光和…...
了解c++11中的新增
一,统一的初始化列表 在引入c11后,我们得出计划都可以用初始化列表进行初始化。 C11 扩大了用大括号括起的列表 ( 初始化列表 ) 的使用范围,使其可用于所有的内置类型和用户自 定义的类型, 使用初始化列表时,可添加等…...
104. 二叉树的最大深度(Java)
目录 解法: 官方解答: 方法一:深度优先搜索 方法二:广度优先搜索 思路与算法 复杂度分析 时间复杂度: 空间复杂度: 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根…...
SpringSecurity6 | 自定义认证规则
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏…...
浅析安科瑞电动机保护器在广州某地铁项目的设计与应用-安科瑞 蒋静
1 摘要 随着城市的发展,较多城市的轨道交通选择修建地下式车辆段(或停车场),即车辆段(或停车场)位于地下或设置有上盖(上盖上再做物业开发)。为了给工作人员提供良好的工作环境、给…...
LeetCode 2048. 下一个更大的数值平衡数
【LetMeFly】2048.下一个更大的数值平衡数 力扣题目链接:https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足:对于每个数位 d ,这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...
多线程(初阶七:阻塞队列和生产者消费者模型)
目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子: 2、引入生产者消费者模型的意义: (1)解耦合 (2)削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...
区间价值 --- 题解--动态规划
目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路: 代码: 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制:C/C 2秒,其他语言4秒 空间限制:C/C 262144K&…...
计算机毕业设计 基于大数据的心脏病患者数据分析管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解
博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...
20:kotlin 类和对象 --泛型(Generics)
类可以有类型参数 class Box<T>(t: T) {var value t }要创建类实例,需提供类型参数 val box: Box<Int> Box<Int>(1)如果类型可以被推断出来,可以省略 val box Box(1)通配符 在JAVA泛型中有通配符?、? extends E、? super E&…...
我对迁移学习的一点理解(系列2)
文章目录 我对迁移学习的一点理解 我对迁移学习的一点理解 源域和目标域是相对的概念,指的是在迁移学习任务中涉及到的两个不同的数据集或领域。 源域(Source Domain)通常指的是已经进行过训练和学习的数据集,它被用来提取特征、…...
Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(二)视图模板、静态资源访问
学习视频:孙哥说SpringMVC:结合Thymeleaf,重塑你的MVC世界!|前所未有的Web开发探索之旅 衔接上文Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(一) SpingMVC中…...
原型模式(Prototype Pattern)
1 基本概念 1.1 大佬文章 设计模式是什么鬼(原型) 详解设计模式:原型模式-腾讯云开发者社区-腾讯云 1.2 知识汇总 (1)原型模式:先 new 一个实例,该实例符合需求,之后再根据这个实…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
