Leetcode 3202. Find the Maximum Length of Valid Subsequence II
- Leetcode 3202. Find the Maximum Length of Valid Subsequence II
- 1. 解题思路
- 2. 代码实现
- 题目链接:3202. Find the Maximum Length of Valid Subsequence II
1. 解题思路
这一题的话是上一题3201. Find the Maximum Length of Valid Subsequence I的升级版,主要就是将除数2调整为任意正数k,但是本质上还是一样的,我们同样有奇数位和偶数位上的数必然对k有着相同的余数,此时,我们只需要考察前两个元素的余数组合,然后考察他们的所有位置能够组成的交叉序列的最大长度即可。
当前两个元素的余数相同时,我们能够获得的最大子序列的长度就是k的余数相同的元素出现的最大频次。
当前两个元素的余数不同时,我们能够快速得到两个余数的位置序列,然后我们通过贪婪算法配合二分搜索即可快速得到他们能够组成的最大交叉序列长度。
最后,如果两个序列的长度之后都小于当前已经获得的最大序列长度了,我们就可以直接跳过这些可能性了,由此,我们即可进一步对问题进行剪枝,从而得到我们最终的答案。
2. 代码实现
给出python代码实现如下:
class Solution:def maximumLength(self, nums: List[int], k: int) -> int:locs = defaultdict(list)for i, x in enumerate(nums):locs[x%k].append(i)ans = max(len(x) for x in locs.values())def get_max_length(s1, s2):n, m = len(s1), len(s2)i, j = 0, 0cnt = 1 if s2[0] < s1[0] else 0while i < n:cnt += 1j = bisect.bisect_left(s2, s1[i])if j < m:cnt += 1else:breaki = bisect.bisect_left(s1, s2[j])return cntfor i in range(k-1):if locs[i] == []:continuefor j in range(i+1, k):if len(locs[i]) + len(locs[j]) <= ans:continuecnt = get_max_length(locs[i], locs[j])ans = max(ans, cnt)return ans
提交代码评测得到:耗时277ms,占用内存16.8MB。
相关文章:
Leetcode 3202. Find the Maximum Length of Valid Subsequence II
Leetcode 3202. Find the Maximum Length of Valid Subsequence II 1. 解题思路2. 代码实现 题目链接:3202. Find the Maximum Length of Valid Subsequence II 1. 解题思路 这一题的话是上一题3201. Find the Maximum Length of Valid Subsequence I的升级版&am…...
通过Spring Boot结合实时流媒体技术对考试过程进行实时监控
本章将深入探讨考试系统中常见的复杂技术问题,并提供基于Spring Boot 3.x的解决方案。涵盖屏幕切换检测与防护、接打电话识别处理、行为监控摄像头使用、网络不稳定应对等,每篇文章详细剖析问题并提供实际案例与代码示例,帮助开发者应对挑战&…...
智能扫地机器人避障与防跌落问题解决方案
智能扫地机器人出现避障与防跌落问题时,可以通过以下几种方式来解决: 一、避障问题的解决方案 1.升级避障技术: ① 激光雷达避障:激光雷达通过发射和接收激光信号来判断与障碍物的距离,具有延迟低、效果稳定、准确度…...
德旺训练营称重问题
这是考小学的分治策略,小学的分治策略几乎都是分三组。本着这个策略,我们做看看。 第一次称重: 分三组,16,16,17,拿两个16称,得到A情况,一样重,那么假铜钱在那组17个里面。B情况不…...
数据决策系统详解
文章目录 数据决策系统的核心组成部分:1. **数据收集与整合**:2. **数据处理与分析**:3. **数据可视化**:4. **决策支持**: 数据决策系统的功能:决策类型:数据决策系统对企业的重要性࿱…...
JSON 简述与应用
1. JSON 简述 JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,常用于客户端与服务器之间的数据传递。它基于JavaScript对象表示法,但独立于语言,可以被多种编程语言解析和生成。 1.1 特点 轻量级&#…...
ResNet50V2
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 一、ResNetV1和ResNetV2的区别 ResNetV2 和 ResNetV1 都是深度残差网络(ResNet)的变体,它们的主要区别在于残差块的设计和…...
基于深度学习的虚拟换装
基于深度学习的虚拟换装技术旨在通过计算机视觉和图像处理技术,将不同的服装虚拟地穿在用户身上,实现快速的试穿和展示。这项技术在电商、时尚和虚拟现实领域具有广泛的应用,能够提升用户体验,增加互动性。以下是关于这一领域的系…...
单段时间最优S型速度规划算法
一,背景 在做机械臂轨迹规划的单段路径的速度规划时,除了参考《Trajectory Planning for Automatic Machines and Robots》等文献之外,还在知乎找到了这位大佬 韩冰 写的在线规划方法: https://zhuanlan.zhihu.com/p/585253101/e…...
pom文件-微服务项目结构
一、微服务项目结构 my-microservices-project/ ├── pom.xml <!-- 父模块的pom.xml --> ├── ry-system/ │ ├── pom.xml <!-- 子模块ry-system的pom.xml --> │ └── src/main/java/com/example/rysystem/ │ └── RySystemApplication.…...
解析Kotlin中的Nothing【笔记摘要】
1.Nothing的本质 Nothing 的源码很简单: public class Nothing private constructor()可以看到它是个class,但它的构造函数是 private 的,这就导致我们没法创建它的实例,并且在源码里 Kotlin 也没有帮我们创建它的实例。 基于这…...
toRefs 和 toRef
文章目录 toRefs 和 toReftoRefstoRef toRefs 和 toRef toRefs toRefs 把一个由reactive对象的值变为一个一个ref的响应式的值 import { ref, reactive, toRefs, toRef } from vue; let person reactive({name: 张三,age: 18, }); // toRefs 把一个由reactive对象的值变为一…...
Vision Transformer论文阅读笔记
目录 An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale -- Vision Transformer摘要Introduction—简介RELATED WORK—相关工作METHOD—方法VISION TRANSFORMER (VIT)—视觉Transformer(ViT) 分析与评估PRE-TRAINING DATA REQUIREMENTS—预训练数据…...
MapReduce的执行流程排序
MapReduce 是一种用于处理大规模数据集的分布式计算模型。它将作业分成多个阶段,以并行处理和分布式存储的方式来提高计算效率。以下是 MapReduce 的执行流程以及各个阶段的详细解释: 1. 作业提交(Job Submission) 用户通过客户端…...
雅思词汇及发音积累 2024.7.3
银行 check (美)支票 cheque /tʃek/ (英)支票 ATM 自动取款机 cashier 收银员 teller /ˈtelə(r)/ (银行)出纳员 loan 贷款 draw/withdraw money 提款 pin number/passsword/code …...
Vue2和Vue3的区别Vue3的组合式API
一、Vue2和Vue3的区别 1、创建方式的不同: (1)、vue2:是一个构造函数,通过该构造函数创建一个Vue实例 new Vue({})(2)、Vue3:是一个对象。并通过该对象的createApp()方法,创建一个vue实例。 Vue…...
ML307R OpenCPU HTTP使用
一、函数介绍 二、示例代码 三、代码下载地址 一、函数介绍 具体函数可以参考cm_http.h文件,这里给出几个我用到的函数 1、创建客户端实例 /*** @brief 创建客户端实例** @param [in] url 服务器地址(服务器地址url需要填写完整,例如(服务器url仅为格式示…...
【状态估计】线性高斯系统的状态估计——离散时间的递归滤波
前两篇文章介绍了离散时间的批量估计、离散时间的递归平滑,本文着重介绍离散时间的递归滤波。 前两篇位置:【状态估计】线性高斯系统的状态估计——离散时间的批量估计、【状态估计】线性高斯系统的状态估计——离散时间的递归平滑。 离散时间的递归滤波…...
架构设计上中的master三种架构,单节点,主从节点,多节点分析
文章目录 背景单节点优点缺点 主从节点优点缺点 多节点优点缺点 多节点,多backup设计优点缺点 总结 背景 在很多分布式系统里会有master,work这种结构。 master 节点负责管理资源,分发任务。下面着重讨论下master 数量不同带来的影响 单节点 优点 1.设…...
如何在 SQL 中删除一条记录?
如何在 SQL 中删除一条记录? 在 SQL 中,您可以使用DELETE查询和WHERE子句删除表中的一条记录。在本文中,我将向您介绍如何使用DELETE查询和WHERE子句删除记录。我还将向您展示如何一次从表中删除多条记录 如何在 SQL 中使用 DELETE 这是使…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
