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.…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
