Leetcode.2100 适合打劫银行的日子
题目链接
Leetcode.2100 适合打劫银行的日子 Rating : 1702
题目描述
你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security,其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time。
如果第 i天满足以下所有条件,我们称它为一个适合打劫银行的日子:
- 第
i天前和后都分别至少有time天。 - 第
i天前连续time天警卫数目都是非递增的。 - 第
i天后连续time天警卫数目都是非递减的。
更正式的,第 i天是一个合适打劫银行的日子当且仅当:security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
请你返回一个数组,包含 所有 适合打劫银行的日子(下标从 0开始)。返回的日子可以 任意 顺序排列。
示例 1:
输入:security = [5,3,3,3,5,6,2], time = 2
输出:[2,3]
解释:
第 2 天,我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天,我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件,所以日子 2 和 3 是适合打劫银行的日子。
示例 2:
输入:security = [1,1,1,1,1], time = 0
输出:[0,1,2,3,4]
解释:
因为 time 等于 0 ,所以每一天都是适合打劫银行的日子,所以返回每一天。
示例 3:
输入:security = [1,2,3,4,5,6], time = 2
输出:[]
解释:
没有任何一天的前 2 天警卫数目是非递增的。
所以没有适合打劫银行的日子,返回空数组。
提示:
- 1<=security.length<=1051 <= security.length <= 10^51<=security.length<=105
- 0<=security[i],time<=1050 <= security[i], time <= 10^50<=security[i],time<=105
分析:
适合打劫的那天 security[i](包括第 i天在内),前 time+1天是非递增的,后 time+1天是非递减的。
我们使用 前后缀分解 求解本题。
定义两个数组 left,right。
left[i]表示,以security[i]结尾,非递增的连续天数。right[i]表示,以security[i]结尾,非递减的连续天数。
我们能够遍历的合法区间是 [time,n-time-1]。只要在这个区间内,left[i] >= time+1 && right[i] >= time+1说明第 i天是适合打劫的。
时间复杂度:O(n)O(n)O(n)
C++代码:
class Solution {
public:vector<int> goodDaysToRobBank(vector<int>& security, int time) {int n = security.size();vector<int> left(n),right(n);left[0] = 1;for(int i = 1;i < n;i++){left[i] = 1;if(security[i-1] >= security[i]) left[i] += left[i-1];}right[n-1] = 1;for(int i = n - 2;i >= 0;i--){right[i] = 1;if(security[i+1] >= security[i]) right[i] += right[i+1];}vector<int> ans;for(int i = time;i < n - time;i++){if(left[i] >= time + 1 && right[i] >= time + 1) ans.push_back(i);}return ans;}
};
Java代码:
class Solution {public List<Integer> goodDaysToRobBank(int[] security, int time) {int n = security.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for(int i = 1;i < n;i++){left[i] = 1;if(security[i-1] >= security[i]) left[i] += left[i-1];}right[n-1] = 1;for(int i = n - 2;i >= 0;i--){right[i] = 1;if(security[i+1] >= security[i]) right[i] += right[i+1];}List<Integer> res = new ArrayList<>();for(int i = time;i < n - time;i++){if(left[i] >= time + 1 && right[i] >= time + 1) res.add(i);}return res;}
}
相关文章:
Leetcode.2100 适合打劫银行的日子
题目链接 Leetcode.2100 适合打劫银行的日子 Rating : 1702 题目描述 你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security,其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time。 如果第 i天满足以下所…...
linux ubuntu查日志信息以及错误排查
目录 一、linux的日志文件 1、常用日志文件 2、其他日志文件 二、历史日志的查看 1、查看Logrotate的配置信息 2、查看日志配置 一、linux的日志文件 Linux系统中最有趣的(可能也是最重要的)目录之一是/var/log。根据文件系统层次结构标准,在系统中运行的大多数…...
DOS经典软件,落下帷幕,新型国产平台,蓬勃发展
提起DOS时代,总让人难以忘怀,陷入深深回忆中,风靡一时的许多软件,如今早已不在,这几款被称为DOS必装的软件,更是让人惋惜。 你还记得这图吗?堪称DOS系统最经典的软盘复制与映像生成软件…...
MongoDB数据存储格式
前言 之前分享了MongoDB的基本命名和视图等信息,本文分享一下MongoDB的数据存储类型,使用方式。基础的MongoDB信息就学习完啦,之后会继续分享MongoDB进阶的一些东西。 MongoDB数据存储格式前言1 文件结构1.2 字段名称2 点符号2.2 嵌入式文件…...
ARC126D Pure Straight
ARC126D Pure Straight 题目大意 给一个长度为nnn的整数序列A(a1,a2,…,an)A(a_1,a_2,\dots,a_n)A(a1,a2,…,an),其中ai∈[1,k]a_i\in [1,k]ai∈[1,k]。 你可以做如下操作任意次: 交换相邻两个元素 求最小的操作次数,使得序列AA…...
基于RK3588的嵌入式linux系统开发(四)——uboot镜像下载(基于RKDevTool工具)
官方提供的SDK中包含RKDevTool工具(RKDevTool_Release_v2.92)和相应的驱动(DriverAssitant_v5.1.1)。本节主要介绍在windows操作系统环境下利用RKDevTool下载以上生成的uboot镜像和bootloader镜像。注意:本节使用的板卡…...
设计模式之策略模式与责任链模式详解和应用
目录1.策略模式1.1 目标1.2.内容定位1.3.定义1.4.应用场景1.5.促销优惠业务场景1.6 用策略模式实现选择支付方式的业务场景1.7 策略模式在框架源码中的体现1.8 策略模式的优缺点2 责任链模式2.1 责任链楼式的应用场景2.2 利用责任链模式进行数据校验拦截2.3 责任链模式和建造者…...
广度优先搜索(BFS)-蓝桥杯
一、BFS搜索的原理BFS搜索的原理:“逐层扩散”,从起点出发,按层次从近到远,逐层先后搜索。编码:用队列实现。应用:BFS一般用于求最短路径问题,BFS的特点是逐层搜索,先搜到的层离起点…...
Java Type类
文章目录Type简介Type分类1. 原始类型(Class)2. 参数化类型(ParameterizedType)3. 类型变量(TypeVariable)4. 通配符类型(WildcardType)5. 泛型数组类型(GenericArrayType)Type简介 Type是Java编程语言中所有类型的公共高级接口。它们包括原始类型、参数化类型、数组类型、类型…...
Springboot扩展点之CommandLineRunner和ApplicationRunner
Springboot扩展点系列:Springboot扩展点之ApplicationContextInitializerSpringboot扩展点之BeanFactoryPostProcessorSpringboot扩展点之BeanDefinitionRegistryPostProcessorSpringboot扩展点之BeanPostProcessorSpringboot扩展点之InstantiationAwareBeanPostPro…...
ngixn 常用配置之文件类型与自定义 log
大家好,我是 17 。 总结了一些 nginx 的常用配置。从入口文件开始,今天讲一下文件类型和自定义log 为了讲述方便,环境为 CentOS 7, nginx 版本 1.21。 配置文件入口 /etc/nginx/nginx.conf这是入口文件,这个文件里…...
【100个 Unity实用技能】 | Unity 通过自定义菜单将资源导出
Unity 小科普 老规矩,先介绍一下 Unity 的科普小知识: Unity是 实时3D互动内容创作和运营平台 。包括游戏开发、美术、建筑、汽车设计、影视在内的所有创作者,借助 Unity 将创意变成现实。Unity 平台提供一整套完善的软件解决方案ÿ…...
0.3调试opencv源码的两种方式
调试opencv源码的两种方式 上两篇我们分别讲了如何配置opencv环境,以及如何编译opencv源码方便我们阅读。但我们还是无法调试我们的代码,无法以我们的程序作为入口来一步一步单点调试看opencv是如何执行的。 【opencv源码解析0.1】VS如何优雅的配置ope…...
Redis的常见操作和Session的持久化
安装Redis使用yum命令,直接将redis安装到linux服务器:yum -y install redis启动redis使用以下命令,以后台运行方式启动redis:redis -server /etc/redis.conf &操作redis使用以下命令启动redis客户端:redis-cli设置…...
TypeScript笔记(二)
背景 上一篇文章我们介绍了TypeScript的一些特性,主要是其与JavaScript的比较,接下来我们将会开始学习Type的语法,这篇文章将会介绍TypeScript的数据类型。 原始数据类型 TypeScript是JavaScript的超集,TypeScript的数据类型就…...
【MyBatis】源码学习 03 - 类型处理器 TypeHandler
文章目录前言参考目录学习笔记1、type 包中类的归类总结2、类型处理器2.1、TypeReference 类3、类型注册表3.1、TypeHandlerRegistry#getTypeHandler前言 本文内容对应的是书本第 8 章的内容,主要是关于类型处理器 TypeHandler 的学习。 这一章节的学习有些地方理…...
建造《流浪地球2》中要毁灭人类的超级量子计算机MOSS的核心量子技术是什么?
1.《流浪地球2》中的量子计算机 2023年中国最火的电影非《流浪地球2》莫属,在《流浪地球2》中有一个人工智能机器人MOSS ,它的前身是“550W”超级量子计算机,“MOSS”是它给自己起的名字(“550W”倒转180度就是“MOSS”ÿ…...
数据结构~七大排序算法(Java实现)
目录 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 递归实现 优化版本 归并排序 插入排序 直接插入排序 public class MySort {public static void insertSort(int[] array) {for (int i 1; i < array.length;…...
python练习
项目场景一: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 问题描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶…...
RPC-thrift实践
参考:https://www.cnblogs.com/52fhy/p/11146047.html 参考:https://juejin.cn/post/7138032523648598030 实践 安装thrift brew install thriftthrift -version 编写thrift文件 新建文件夹thrift新建文件 结构体文件 Struct.thrift 服务文件 Service.…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
华为OD机考- 简单的自动曝光/平均像素
import java.util.Arrays; import java.util.Scanner;public class DemoTest4 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint[] arr Array…...
