注册账号自建网站/seo营销是什么意思
- 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 题? 输入格式 输入一…...

【蓝桥杯入门记录】静态数码管例程
目录 一、补充 (code) 二、例程 (1)例程1:数码管显示某一位(某一杠)。以点亮8段数码管最上面的横杠为例。 (2)例程2:数码管的8个段依次点亮(其他…...

6.openEuler系统服务的配置和管理(二)
openEuler OECA认证辅导,标红的文字为学习重点和考点。 如果需要做实验,建议安装麒麟信安、银河麒麟、统信等具有图形化的操作系统,其安装与openeuler基本一致。 3.任务管理 任务的概念和相关术语: 当你在终端或控制台工作时,可能不希望由于运行一个作业而占住了屏幕,因…...

一招鲜吃遍天!ChatGPT高级咒语揭秘:记忆、洗稿、速写SEO文章(一)
🌟 摘要 🌟 这个专栏系列的初衷是针对特定痛点精心设计GPT提示词,在这篇文章中,我们深入探讨了利用GPT技术解决三个常见挑战:增强记忆力、内容创新、以及SEO文章速写的高级技巧。这些挑战分别对应三个独特的解决策略,我们将逐一详细解析。 首先,解决记忆增强的挑战,我…...

LeetCode 每日一题 2024/2/19-2024/2/25
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/19 590. N 叉树的后序遍历2/20 105. 从前序与中序遍历序列构造二叉树2/21 106. 从中序与后序遍历序列构造二叉树2/22 889. 根据前序和后序遍历构造二叉树2/23 2583. 二叉…...

Javaweb之SpringBootWeb案例之配置优先级的详细解析
1. 配置优先级 在我们前面的课程当中,我们已经讲解了SpringBoot项目当中支持的三类配置文件: application.properties application.yml application.yaml 在SpringBoot项目当中,我们要想配置一个属性,可以通过这三种方式当中…...

GO框架基础 (三)、xorm库
xorm介绍 官网:https://xorm.io/ git文档:https://github.com/go-xorm/xorm xorm 是一个 Go 语言的 ORM(对象关系映射)库,它提供了一种简单、高效的方式来将 Go 语言中的结构体与数据库表进行映射,并提供了…...

神经网络系列---回归问题和分类问题
文章目录 回归问题和分类问题回归问题:分类问题:多分类问题:排序问题:自定义损失函数: 回归问题和分类问题 回归问题: 回归问题是一种预测连续数值输出的任务。在这种问题中,模型的目标是根据…...

Jetpack Compose 与 Kotlin 的兼容性对应关系
点击查看:Jetpack Compose 教程 点击查看:Jetpack Compose Kotlin 的兼容性 官网 声明依赖项 如需添加 Compose Compiler 的依赖项,您必须将 Google Maven 代码库添加到项目中。如需了解详情,请参阅 Google 的 Maven 代码库。 …...

汇编反外挂
在软件保护领域,尤其是游戏保护中,反外挂是一个重要的议题。外挂通常指的是一种第三方软件,它可以修改游戏数据、操作游戏内存或提供其他作弊功能,从而给玩家带来不公平的优势。为了打击外挂,游戏开发者会采取一系列措…...

134 Linux 系统编程11 ,readlink命令,文件目录rwx权限差异,目录操作函数
一 readlink 命令 前面知道,如果a.soft是一个软链接,我们使用 cat a.soft,会直接查看这个软链接指向的文件 那么我们就是想看这个软链接是啥,可以使用 readlink a.soft 二 获取工作目录 getcwd函数 获取进程当前工作目录 (卷3,标…...