Leetcode 3048. Earliest Second to Mark Indices I
- Leetcode 3048. Earliest Second to Mark Indices I
- 1. 解题思路
- 2. 代码实现
- 题目链接:3048. Earliest Second to Mark Indices I
1. 解题思路
这一题的话基础的思路就是二分法查找最小的可以将所有的数字都mark上的最小位置。
因此,这里的问题就会变成如何快速地判断对于一个给定的位置,能否在这个操作序列下将所有的数字全部mark上。
而考虑的可能的操作,显然有:
- 要将一个数mark上,必须在某次操作时其给出的mark indice正好为这个位置,且之前已经将其减为0了。
因此,我们就要确保:
- 在对应的操作序列下所有的位置至少都出现过一次;
- 在最后一次出现某一位置的操作前,我们可以将对应位置上的值变为0;
因此,我们只需要对每一个长度的操作序列,判断其各个位置的操作是否齐全以及其最后一次操作的位置,然后分配一下decrease的顺序是否可以满足即可。
2. 代码实现
给出python代码实现如下:
class Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:n, m = len(nums), len(changeIndices)changeIndices = [x-1 for x in changeIndices]idxs = defaultdict(list)for i, x in enumerate(changeIndices):idxs[x].append(i)def get_last_index(n):last_index = {}for k, v in idxs.items():idx = bisect.bisect_right(v, n)-1if idx == -1:breaklast_index[v[idx]] = nums[k]return last_indexdef is_possible(k):last_index = get_last_index(k)if len(last_index) < n:return Falsecnt = 0for i in range(k+1):if i not in last_index:cnt += 1elif cnt < last_index[i]:return Falseelse:cnt -= last_index[i]return Trueif not is_possible(m-1):return -1i, j = sum(nums) + len(nums)-2, m-1while j-i>1:k = (i+j)//2if is_possible(k):j = kelse:i = kreturn j+1
提交代码评测得到:耗时135ms,占用内存17.5MB。
相关文章:
Leetcode 3048. Earliest Second to Mark Indices I
Leetcode 3048. Earliest Second to Mark Indices I 1. 解题思路2. 代码实现 题目链接:3048. Earliest Second to Mark Indices I 1. 解题思路 这一题的话基础的思路就是二分法查找最小的可以将所有的数字都mark上的最小位置。 因此,这里的问题就会变…...

从源码学习单例模式
单例模式 单例模式是一种设计模式,常用于确保一个类只有一个实例,并提供一个全局访问点。这意味着无论在程序的哪个地方,只能创建一个该类的实例,而不会出现多个相同实例的情况。 在单例模式中,常用的实现方式包括懒汉…...
axios介绍和使用
1. Axios是什么 Axios框架全称(ajax – I/O – system) Axios是一个基于Promise的JavaScript HTTP客户端,用于浏览器和Node.js环境。它可以发送HTTP请求并支持诸如请求和响应拦截、转换数据、取消请求以及自动转换JSON数据等功能。 Axios提…...
redis雪崩问题
Redis雪崩问题是指在Redis缓存系统中,由于某些原因导致大量缓存数据同时失效或过期,导致所有请求都直接访问数据库,从而引发数据库性能问题甚至宕机的情况。 造成Redis雪崩问题的原因主要有以下几个: 缓存数据同时失效ÿ…...

[SUCTF 2019]EasySQL1 题目分析与详解
一、题目介绍 1、题目来源: BUUCTF网站,网址:https://buuoj.cn/challenges 2、题目描述: 通过以上信息,拿到flag。 二、解题思路 首先打开靶机,尝试输入1查看回显,回显如图所示:…...

TestNG与ExtentReport单元测试导出报告文档
TestNG与ExtentReport集成 目录 1 通过实现ITestListener的方法添加Reporter log 1.1 MyTestListener设置 1.2 输出结果 2 TestNG与ExtentReporter集成 2.1 项目结构 2.2 MyExtentReportListener设置 2.3 单多Suite、Test组合测试 2.3.1 单Suite单Test 2.3…...

【JavaEE】_form表单构造HTTP请求
目录 1. form表单的格式 1.1 form表单的常用属性 1.2 form表单的常用搭配标签:input 2. form表单构造GET请求实例 3. form表单构造POST请求实例 4. form表单构造法的缺陷 对于客户端浏览器,以下操作即构造了HTTP请求: 1. 直接在浏览器…...
Mysql中INFORMATION_SCHEMA虚拟库使用
虚拟库字段讲解 #查看INFORMATION_SCHEMA的表信息 DESC information_schema.tables; 重要列: TABLE_SCHEMA #表所在的库 TABLE_NAME #表名 ENGINE #表的存储引擎 TABLE_ROWS #表的行数 DATA_LENGTH #表数据行占用的字节数 AVG_ROW_LENGTH #平均行长度 INDEX_LENGTH…...

【《高性能 MySQL》摘录】第 2 章 MySQL 基准测试
文章目录 2.1 为什么需要基准测试2.2 基准测试的策略2.2.1 测试何种指标 2.3 基准测试方法2.3.1 设计和规划基准测试2.3.2 基准测试应该运行多长时间2.3.3 获取系统性能和状态2.3.4 获得准确的测试结果2.3.5 运行基准测试并分析结果2.3.6 绘图的重要性 2.4 基准测试工具…...

常用的Web应用程序的自动测试工具有哪些
在Web应用程序的自动化测试领域,有许多流行的工具可供选择。以下是一些常用的Web自动化测试工具: 1. Selenium - Selenium是最流行的开源Web应用程序自动化测试套件之一。 - 它支持多种编程语言,如Java、C#、Python、Ruby等。 …...
人工智能与开源机器学习框架
链接:华为机考原题 TensorFlow是一个开源的机器学习框架,由Google开发和维护。它提供了一个针对神经网络和深度学习的强大工具集,能够帮助开发人员构建和训练各种机器学习模型。 TensorFlow的基本概念包括: 张量(Ten…...

高通XBL阶段读取分区
【需求】: 在某些场景下,需要在XBL阶段读取分区数据,需要验证xbl阶段方案 这里主要以裸分区为例,比如oem分区。 1、创建一个1MB大小的oem.img,写入内容“test oem partition” 创建方式: dd if/dev/null …...

[极客大挑战2019]upload
该题考点:后缀黑名单文件内容过滤php木马的几种书写方法 phtml可以解析php代码;<script language"php">eval($_POST[cmd]);</script> 犯蠢的点儿:利用html、php空格和php.不解析<script language"php"&…...
[FastDDS] 基于eProsima FastDDS的移动机器人数据中间件
[FastDDS] 基于eProsima FastDDS的移动机器人数据中间件 注明:无 本栏目主要讲述,基于eProsima FastDDS的移动机器人数据中间件的实现、使用、性能测试。 What is [ FastDDS ]: eProsima Fast DDS是DDS(数据分发服务)规范的C实现…...

实现外网手机或者电脑随时随地远程访问家里的电脑主机(linux为例)
文章目录 一、背景概要二、安装配置花生壳软件(linux版本)三、手机端(外网)验证连接四、安装ubuntu20server版系统遇到的问题记录 一、背景概要 由于经常在遇到某些问题的时候,针对某一个场景的理解,需要借助于自己的电脑去编译(aosp/linux/qemu)代码查…...

spring boot集成redis
引入依赖 <!-- redis依赖 --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency><!-- 连接池依赖 --><dependency><groupId>org.ap…...
Docker的常用命令
Docker的常用命令 Docker是一个开源的应用容器引擎,它使得开发者能够打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux机器上,也可以实现虚拟化。容器是完全使用沙箱机制,相互之间没有任何接口ÿ…...
JSON简介与基本使用
JSON简介与基本使用 引言 在现今的互联网开发中,数据交换格式的选择至关重要。其中,JSON(JavaScript Object Notation)作为一种轻量级的数据交换格式,因其简洁、易读和易写的特性而备受青睐。本文将简要介绍JSON的基…...

好物周刊#40:多功能文件管理器
https://github.com/cunyu1943/JavaPark https://yuque.com/cunyu1943 村雨遥的好物周刊,记录每周看到的有价值的信息,主要针对计算机领域,每周五发布。 一、项目 1. 中国节假日补班日历 中国节假日、调休、补班日历,ICS 格式…...

【洛谷 P8780】[蓝桥杯 2022 省 B] 刷题统计 题解(贪心算法+模拟+四则运算)
[蓝桥杯 2022 省 B] 刷题统计 题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a a a 道题目,周六和周日每天做 b b b 道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于 n n n 题? 输入格式 输入一…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...

02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...