当前位置: 首页 > news >正文

滑动窗口练习(三)— 加油站问题

题目
测试链接
在一条环路上有 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 个加油站&#xff0c;其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车&#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发&#xff0c;开始时油箱为空。 给定两个整数数组…...

udemy angular decoration 自存

番外 为什么一个ts文件变成了component,因为它使用了components装饰器 components is just a class,you export it so angular know how to use it 举例&#xff1a;组件装饰器 decoration前总是有一个符号 decoration的作用&#xff08;之一&#xff1f;&#xff09; NgModu…...

msvcr90.dll丢失的解决方法分享,5个快速修复dll文件丢失教程

在今天的电脑使用过程中&#xff0c;我们可能会遇到各种各样的问题。其中之一就是msvcr90.dll丢失的问题。那么&#xff0c;msvcr90.dll是什么&#xff1f;msvcr90.dll丢失对电脑有什么影响&#xff1f;又该如何解决这个问题呢&#xff1f;接下来&#xff0c;我将为大家详细介绍…...

海外媒体发稿:软文发稿推广技巧解析超级实用-华媒舍

随着互联网时代的发展&#xff0c;软文发稿成为推广产品与服务的重要手段之一。本文将向大家介绍软文发稿推广的技巧&#xff0c;帮助您更好地利用软文推广商业活动。无论是拥有自己的品牌还是个人创业者&#xff0c;都可以从中受益。 1. 什么是软文&#xff1f; 软文是指以文…...

vm net 方式 静态ip配置访问主机IP和外网

1、win 11 安装vm&#xff0c;镜像文件 F:\software\VMwork\CentOS-7-x86_64-Everything-1804.iso 2、配置网络 net 方式 3、右击网络--》属性---》更改适配器设置--》vmnet8 属性、这里不做配置会出现主机ping通访问不通的情况&#xff0c;&#xff08;访问不通&#xff0c;…...

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、手撕防抖与节流、树与对象的转换、递归调用&#xff0c;链表头插法 1.1、防抖 防抖函数用于延迟执行某个函数&#xff0c;直到过了一定的间隔时间&#xff08;例如等待用户停止输入&#xff09;后再执行。 即后一次点击事件发生时间距离一次点击事件至少间隔一定时间。 …...

基于BEV+Transformer的地面要素感知+建模技术在高德的应用

导读 本文将主要介绍BEVTransformer端到端感知与建模技术在高德各项业务中的应用&#xff0c;如高精地图中地面要素&#xff08;包含线要素和地面标识&#xff09;自动化上的具体方案及其演化过程。该方案使用BEVTransformer技术来实现采集车上不同传感器&#xff08;包含激光和…...

了解c++11中的新增

一&#xff0c;统一的初始化列表 在引入c11后&#xff0c;我们得出计划都可以用初始化列表进行初始化。 C11 扩大了用大括号括起的列表 ( 初始化列表 ) 的使用范围&#xff0c;使其可用于所有的内置类型和用户自 定义的类型&#xff0c; 使用初始化列表时&#xff0c;可添加等…...

104. 二叉树的最大深度(Java)

目录 解法&#xff1a; 官方解答&#xff1a; 方法一&#xff1a;深度优先搜索 方法二&#xff1a;广度优先搜索 思路与算法 复杂度分析 时间复杂度&#xff1a; 空间复杂度&#xff1a; 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根…...

SpringSecurity6 | 自定义认证规则

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…...

浅析安科瑞电动机保护器在广州某地铁项目的设计与应用-安科瑞 蒋静

1 摘要 随着城市的发展&#xff0c;较多城市的轨道交通选择修建地下式车辆段&#xff08;或停车场&#xff09;&#xff0c;即车辆段&#xff08;或停车场&#xff09;位于地下或设置有上盖&#xff08;上盖上再做物业开发&#xff09;。为了给工作人员提供良好的工作环境、给…...

LeetCode 2048. 下一个更大的数值平衡数

【LetMeFly】2048.下一个更大的数值平衡数 力扣题目链接&#xff1a;https://leetcode.cn/problems/next-greater-numerically-balanced-number/ 如果整数 x 满足&#xff1a;对于每个数位 d &#xff0c;这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。…...

多线程(初阶七:阻塞队列和生产者消费者模型)

目录 一、阻塞队列的简单介绍 二、生产者消费者模型 1、举个栗子&#xff1a; 2、引入生产者消费者模型的意义&#xff1a; &#xff08;1&#xff09;解耦合 &#xff08;2&#xff09;削峰填谷 三、模拟实现阻塞队列 1、阻塞队列的简单介绍 2、实现阻塞队列 &#…...

区间价值 --- 题解--动态规划

目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路&#xff1a; 代码&#xff1a; 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制&#xff1a;C/C 2秒&#xff0c;其他语言4秒 空间限制&#xff1a;C/C 262144K&…...

计算机毕业设计 基于大数据的心脏病患者数据分析管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

20:kotlin 类和对象 --泛型(Generics)

类可以有类型参数 class Box<T>(t: T) {var value t }要创建类实例&#xff0c;需提供类型参数 val box: Box<Int> Box<Int>(1)如果类型可以被推断出来&#xff0c;可以省略 val box Box(1)通配符 在JAVA泛型中有通配符?、? extends E、? super E&…...

我对迁移学习的一点理解(系列2)

文章目录 我对迁移学习的一点理解 我对迁移学习的一点理解 源域和目标域是相对的概念&#xff0c;指的是在迁移学习任务中涉及到的两个不同的数据集或领域。 源域&#xff08;Source Domain&#xff09;通常指的是已经进行过训练和学习的数据集&#xff0c;它被用来提取特征、…...

Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(二)视图模板、静态资源访问

学习视频&#xff1a;孙哥说SpringMVC&#xff1a;结合Thymeleaf&#xff0c;重塑你的MVC世界&#xff01;&#xff5c;前所未有的Web开发探索之旅 衔接上文Spring MVC学习随笔-控制器(Controller)开发详解&#xff1a;控制器跳转与作用域&#xff08;一&#xff09; SpingMVC中…...

原型模式(Prototype Pattern)

1 基本概念 1.1 大佬文章 设计模式是什么鬼&#xff08;原型&#xff09; 详解设计模式&#xff1a;原型模式-腾讯云开发者社区-腾讯云 1.2 知识汇总 &#xff08;1&#xff09;原型模式&#xff1a;先 new 一个实例&#xff0c;该实例符合需求&#xff0c;之后再根据这个实…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...