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

Leetcode 3036. Number of Subarrays That Match a Pattern II

  • Leetcode 3036. Number of Subarrays That Match a Pattern II
    • 1. 解题思路
    • 2. 代码实现
  • 3036. Number of Subarrays That Match a Pattern II

1. 解题思路

这一题其实有点水,因为本质上还是一道套路题目,和前两周的两道题目一样,都是考察的z算法:

  1. Leetcode 3031. Minimum Time to Revert Word to Initial State II
  2. Leetcode 3008. Find Beautiful Indices in the Given Array II

而关于z算法,可以参考我之前写的博客经典算法:Z算法(z algorithm),这里就不过多展开了。

这里,我们只来看一下要怎么用z算法来完成这道题即可。

显然这个题目本质上还是一个模式匹配的题目,我们将原始数组的相邻元素的大小关系组成一个新的数组,那么我们就是要看一下pattern对应的大小关系在这个新的数组当中出现过多少次,这个就是一个标注的z算法的题目了,参考上述博客当中的内容即可,这里就不过多展开了。

2. 代码实现

给出python代码实现如下:

def z_algorithm(s):n = len(s)z = [0 for _ in range(n)]l, r = -1, -1for i in range(1, n):if i > r:l, r = i, iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1else:k = i - lif z[k] < r - i + 1:z[i] = z[k]else:l = iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1z[0] = nreturn zclass Solution:def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:n = len(nums)m = len(pattern)mapping = {1:"g", 0:"e", -1:"l"}s = ""for i in range(n-1):if nums[i+1] > nums[i]:s += "g"elif nums[i+1] == nums[i]:s += "e"else:s += "l"p = "".join([mapping[i] for i in pattern])z = z_algorithm(p + s)[m:]ans = [1 for x in z if x >= m]return len(ans)

提交代码评测得到:耗时1669ms,占用内存70.7MB。

相关文章:

Leetcode 3036. Number of Subarrays That Match a Pattern II

Leetcode 3036. Number of Subarrays That Match a Pattern II 1. 解题思路2. 代码实现 3036. Number of Subarrays That Match a Pattern II 1. 解题思路 这一题其实有点水&#xff0c;因为本质上还是一道套路题目&#xff0c;和前两周的两道题目一样&#xff0c;都是考察的…...

华为环网双机接入IPTV网络部署案例

环网双机接入IPTV网络部署案例 组网图形 图2 环网双机场景IPTV基本组网图 方案简介配置注意事项组网需求数据规划配置思路操作步骤配置文件 方案简介 随着IPTV业务的迅速发展&#xff0c;IPTV平台承载的用户也越来越多&#xff0c;用户对IPTV直播业务的可靠性要求越来越高。…...

“智能检测,精准把控。温湿度检测系统,为您的生活带来全方位的健康保障。”#非标协议项目【上】

“智能检测&#xff0c;精准把控。温湿度检测系统&#xff0c;为您的生活带来全方位的健康保障。”#非标协议项目【上】 前言预备知识1温湿度检测系统需求2.代码整合2.1找到编程实现LCD1602显示一行工程&#xff0c;打开代码文件&#xff0c;将所需的LCD1602驱动代码拷贝到温湿…...

牛客网SQL进阶137:第二快/慢用时之差大于试卷时长一半的试卷

官网链接&#xff1a; 第二快慢用时之差大于试卷时长一半的试卷_牛客题霸_牛客网现有试卷信息表examination_info&#xff08;exam_id试卷ID, tag试卷类别,。题目来自【牛客题霸】https://www.nowcoder.com/practice/b1e2864271c14b63b0df9fc08b559166?tpId240 0 问题描述 试…...

CVE-2022-0760 漏洞复现

CVE-2022-0760 NSS [HNCTF 2022 WEEK2]ohmywordpress 【CVE-2022-0760】 题目描述&#xff1a;flag在数据库里面。 开题&#xff1a; 顺着按钮一直点下去会发现出现一个按钮叫安装WordPress 安装完之后的界面&#xff0c;有一个搜索框。 F12看看network。 又出现了这个Wor…...

WordPress突然后台无法管理问题

登录WordPress后台管理评论&#xff0c;发现点击编辑、回复均无反应。 尝试清除缓存、关闭CF连接均无效。 查看插件时发现关闭wp-china-yes插件可以解决问题。 后来又测试了下发现加速管理后台这项&#xff0c;在启用时会发生点击无效问题&#xff0c;禁用就好了&#xff0c;不…...

STM32F1 - 标准外设库_规范

STM32F10x_StdPeriph_Lib_V3.6.0 1> 头文件包含关系2> .c文件内部结构3> 宏定义位置4> 位掩码bit mask5> .c文件中定义私有变量6> 枚举类型定义 1> 头文件包含关系 1个头文件stm32f10x.h 就把整个MCU以及标准外设库&#xff0c;就管理了&#xff1b; 2>…...

推荐系统|召回04_离散特征处理

离散特征处理 离散特征是什么 怎么处理离散特征 One-hot编码 Embedding嵌入 从one-hot到Embedding&#xff0c;已经节省了很多的存储空间&#xff0c;但当数据量大的时候&#xff0c;还是占空间&#xff0c;所以工业界仍会对Embedding进行优化 而一个物品所对应的Embedding参数…...

一个查看armv8系统寄存器-值-含义的方式

找到解压后的SysReg_xml_v86A-2019-12目录 wget https://developer.arm.com/-/media/developer/products/architecture/armv8-a-architecture/2019-12/SysReg_xml_v86A-2019-12.tar.gz wget https://developer.arm.com/-/media/developer/products/architecture/armv8-a-archi…...

LLMs之miqu-1-70b:miqu-1-70b的简介、安装和使用方法、案例应用之详细攻略

LLMs之miqu-1-70b&#xff1a;miqu-1-70b的简介、安装和使用方法、案例应用之详细攻略 目录 miqu-1-70b的简介 miqu-1-70b的安装和使用方法 1、安装 2、使用方法 miqu-1-70b的案例应用 miqu-1-70b的简介 2024年1月28日&#xff0c;发布了miqu 70b&#xff0c;潜在系列中的…...

npm 下载报错

报错信息 : 证书过期 (CERT_HAS_EXPIRED) D:\Apps\nodejs-v18.16.1\npx.cmd --yes create-next-app"latest" . --ts npm ERR! code CERT_HAS_EXPIRED npm ERR! errno CERT_HAS_EXPIRED npm ERR! request to https://registry.npm.taobao.org/create-next-app failed…...

GPT-4登场:多模态能力革新,提升ChatGPT与必应体验,开放API助力游戏革新

GPT-4登场&#xff1a;多模态能力革新&#xff0c;提升ChatGPT与必应体验&#xff0c;开放API助力游戏革新 引言 在人工智能领域&#xff0c;GPT-4的发布标志着一个新时代的到来。这一多模态大模型不仅在技术性能上实现了飞跃&#xff0c;更在功能层面带来全新的突破。GPT-4的…...

【芯片设计- RTL 数字逻辑设计入门 11.1 -- 状态机实现 移位运算与乘法 1】

文章目录 移位运算与乘法状态机简介SystemVerilog中的测试平台VCS 波形仿真 阻塞赋值和非阻塞赋值有限状态机&#xff08;FSM&#xff09;与无限状态机的区别 本篇文章接着上篇文章【芯片设计- RTL 数字逻辑设计入门 11 – 移位运算与乘法】 继续介绍&#xff0c;这里使用状态机…...

MongoDB系列:管道操作:聚合阶段操作符(二)

MongoDB系列&#xff1a;管道操作&#xff1a;聚合阶段操作符&#xff08;二&#xff09; 聚合阶段操作符介绍 本节只编写了个人认为可能用到的操作符&#xff0c;详细更多的操作符以及使用注意事项请前往MongoDB官网。 $match 过滤匹配数据。 // 插入数据 db.orders.inse…...

C++ //练习 5.12 修改统计元音字母的程序,使其能统计以下含有两个字符的字符序列的数量:ff、fl和fi。

C Primer&#xff08;第5版&#xff09; 练习 5.12 练习 5.12 修改统计元音字母的程序&#xff0c;使其能统计以下含有两个字符的字符序列的数量&#xff1a;ff、fl和fi。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /****…...

C语言-----自定义类型-----结构体枚举联合

结构体和数组一样&#xff0c;都是一群数据的集合&#xff0c;不同的是数组当中的数据是相同的类型&#xff0c;但是结构体中的数据类型可以不相同&#xff0c;结构体里的成员叫做成员变量 结构体类型是C语言里面的一种自定义类型&#xff0c;我们前面已经了解到过int,char,fl…...

elasticsearch下载及可视化工具下载使用

elasticsearch下载及配置、启动 一、下载 Download Elasticsearch | Elastic 二、启动 双击bat即可。 出现如下说明启动成功&#xff1a; 访问测试&#xff1a; 三、注意 &#xff08;1&#xff09;因为es启动默认端口是&#xff1a;9200,所以需要检查此端口是否被占用。…...

vim常用命令以及配置文件

layout: article title: “vim文本编译器” vim文本编辑器 有三种模式: 命令模式 文本模式, 末行模式 vim命令大全 - 知乎 (zhihu.com) 命令模式 插入 i: 切换到输入模式&#xff0c;在光标当前位置开始输入文本。 a: 进入插入模式&#xff0c;在光标下一个位置开始输入文…...

2024年的VUE2下的无效指令npm install --save vue-i18n

vue官网已经声明了不再维护vue2, vue-i18n安装依赖的时候就只接安装vue3的vue-i18, 直接报错&#xff1a; > npm install --save vue-i18n npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! npm ERR! While resolving: yudao-ui-admin…...

计算机视觉主要知识点

计算机视觉是指利用计算机和算法来解析和理解图片和视频中的内容。这是一个跨学科领域&#xff0c;融合了计算机科学、图像处理、机器学习和模式识别等多方面的技术。以下是一些计算机视觉入门的基本知识点&#xff1a; 图像基础&#xff1a; 像素&#xff1a;图片的最基本组成…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...