当前位置: 首页 > news >正文

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. 代码实现 题目链接&#xff1a;3202. Find the Maximum Length of Valid Subsequence II 1. 解题思路 这一题的话是上一题3201. Find the Maximum Length of Valid Subsequence I的升级版&am…...

通过Spring Boot结合实时流媒体技术对考试过程进行实时监控

本章将深入探讨考试系统中常见的复杂技术问题&#xff0c;并提供基于Spring Boot 3.x的解决方案。涵盖屏幕切换检测与防护、接打电话识别处理、行为监控摄像头使用、网络不稳定应对等&#xff0c;每篇文章详细剖析问题并提供实际案例与代码示例&#xff0c;帮助开发者应对挑战&…...

智能扫地机器人避障与防跌落问题解决方案

智能扫地机器人出现避障与防跌落问题时&#xff0c;可以通过以下几种方式来解决&#xff1a; 一、避障问题的解决方案 1.升级避障技术&#xff1a; ① 激光雷达避障&#xff1a;激光雷达通过发射和接收激光信号来判断与障碍物的距离&#xff0c;具有延迟低、效果稳定、准确度…...

德旺训练营称重问题

这是考小学的分治策略&#xff0c;小学的分治策略几乎都是分三组。本着这个策略&#xff0c;我们做看看。 第一次称重&#xff1a; 分三组&#xff0c;16,16,17&#xff0c;拿两个16称&#xff0c;得到A情况&#xff0c;一样重&#xff0c;那么假铜钱在那组17个里面。B情况不…...

数据决策系统详解

文章目录 数据决策系统的核心组成部分&#xff1a;1. **数据收集与整合**&#xff1a;2. **数据处理与分析**&#xff1a;3. **数据可视化**&#xff1a;4. **决策支持**&#xff1a; 数据决策系统的功能&#xff1a;决策类型&#xff1a;数据决策系统对企业的重要性&#xff1…...

JSON 简述与应用

1. JSON 简述 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;常用于客户端与服务器之间的数据传递。它基于JavaScript对象表示法&#xff0c;但独立于语言&#xff0c;可以被多种编程语言解析和生成。 1.1 特点 轻量级&#…...

ResNet50V2

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、ResNetV1和ResNetV2的区别 ResNetV2 和 ResNetV1 都是深度残差网络&#xff08;ResNet&#xff09;的变体&#xff0c;它们的主要区别在于残差块的设计和…...

基于深度学习的虚拟换装

基于深度学习的虚拟换装技术旨在通过计算机视觉和图像处理技术&#xff0c;将不同的服装虚拟地穿在用户身上&#xff0c;实现快速的试穿和展示。这项技术在电商、时尚和虚拟现实领域具有广泛的应用&#xff0c;能够提升用户体验&#xff0c;增加互动性。以下是关于这一领域的系…...

单段时间最优S型速度规划算法

一&#xff0c;背景 在做机械臂轨迹规划的单段路径的速度规划时&#xff0c;除了参考《Trajectory Planning for Automatic Machines and Robots》等文献之外&#xff0c;还在知乎找到了这位大佬 韩冰 写的在线规划方法&#xff1a; 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 的源码很简单&#xff1a; public class Nothing private constructor()可以看到它是个class&#xff0c;但它的构造函数是 private 的&#xff0c;这就导致我们没法创建它的实例&#xff0c;并且在源码里 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 是一种用于处理大规模数据集的分布式计算模型。它将作业分成多个阶段&#xff0c;以并行处理和分布式存储的方式来提高计算效率。以下是 MapReduce 的执行流程以及各个阶段的详细解释&#xff1a; 1. 作业提交&#xff08;Job Submission&#xff09; 用户通过客户端…...

雅思词汇及发音积累 2024.7.3

银行 check &#xff08;美&#xff09;支票 cheque /tʃek/ &#xff08;英&#xff09;支票 ATM 自动取款机 cashier 收银员 teller /ˈtelə(r)/ &#xff08;银行&#xff09;出纳员 loan 贷款 draw/withdraw money 提款 pin number/passsword/code …...

Vue2和Vue3的区别Vue3的组合式API

一、Vue2和Vue3的区别 1、创建方式的不同&#xff1a; &#xff08;1&#xff09;、vue2:是一个构造函数&#xff0c;通过该构造函数创建一个Vue实例 new Vue({})&#xff08;2&#xff09;、Vue3:是一个对象。并通过该对象的createApp()方法&#xff0c;创建一个vue实例。 Vue…...

ML307R OpenCPU HTTP使用

一、函数介绍 二、示例代码 三、代码下载地址 一、函数介绍 具体函数可以参考cm_http.h文件,这里给出几个我用到的函数 1、创建客户端实例 /*** @brief 创建客户端实例** @param [in] url 服务器地址(服务器地址url需要填写完整,例如(服务器url仅为格式示…...

【状态估计】线性高斯系统的状态估计——离散时间的递归滤波

前两篇文章介绍了离散时间的批量估计、离散时间的递归平滑&#xff0c;本文着重介绍离散时间的递归滤波。 前两篇位置&#xff1a;【状态估计】线性高斯系统的状态估计——离散时间的批量估计、【状态估计】线性高斯系统的状态估计——离散时间的递归平滑。 离散时间的递归滤波…...

架构设计上中的master三种架构,单节点,主从节点,多节点分析

文章目录 背景单节点优点缺点 主从节点优点缺点 多节点优点缺点 多节点&#xff0c;多backup设计优点缺点 总结 背景 在很多分布式系统里会有master,work这种结构。 master 节点负责管理资源&#xff0c;分发任务。下面着重讨论下master 数量不同带来的影响 单节点 优点 1.设…...

如何在 SQL 中删除一条记录?

如何在 SQL 中删除一条记录&#xff1f; 在 SQL 中&#xff0c;您可以使用DELETE查询和WHERE子句删除表中的一条记录。在本文中&#xff0c;我将向您介绍如何使用DELETE查询和WHERE子句删除记录。我还将向您展示如何一次从表中删除多条记录 如何在 SQL 中使用 DELETE 这是使…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

LINUX编译vlc

下载 VideoLAN / VLC GitLab 选择最新的发布版本 准备 sudo apt install -y xcb bison sudo apt install -y autopoint sudo apt install -y autoconf automake libtool编译ffmpeg LINUX FFMPEG编译汇总&#xff08;最简化&#xff09;_底部的附件列表中】: ffmpeg - lzip…...