滑动窗口练习(三)— 加油站问题
题目
测试链接
在一条环路上有 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 一个实例,该实例符合需求,之后再根据这个实…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...
