当前位置: 首页 > 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;图片的最基本组成…...

汇川程序框架实战:从轴控到整机集成的自动化开发指南

1. 汇川程序框架入门&#xff1a;为什么选择模块化开发&#xff1f; 第一次接触汇川PLC时&#xff0c;我和很多新手一样被各种功能块绕得头晕。直到在汽车零部件产线项目上踩了三天坑才发现&#xff1a;模块化编程才是工业自动化的救命稻草。想象一下乐高积木——轴控、气缸、T…...

前端部署:从开发到生产的最后一公里

前端部署&#xff1a;从开发到生产的最后一公里 毒舌时刻 前端部署&#xff1f;这不是运维的事吗&#xff1f; "我只负责写代码&#xff0c;部署交给运维"——结果部署失败&#xff0c;互相甩锅&#xff0c;"我直接把文件上传到服务器"——结果更新不及时&…...

Python F1数据分析终极指南:5个高级技巧掌握赛车性能可视化

Python F1数据分析终极指南&#xff1a;5个高级技巧掌握赛车性能可视化 【免费下载链接】Fast-F1 FastF1 is a python package for accessing and analyzing Formula 1 results, schedules, timing data and telemetry 项目地址: https://gitcode.com/GitHub_Trending/fa/Fas…...

PyTorch Autograd动态计算图实战:从构建、可视化到高效调试

1. 动态计算图的构建原理 PyTorch的Autograd系统最迷人的特性就是它的动态计算图。我第一次接触这个概念时&#xff0c;感觉就像发现了一个魔法黑箱——它能在代码运行时自动记录所有操作&#xff0c;并在需要时反向计算梯度。这种动态特性让PyTorch在调试复杂模型时特别顺手&a…...

5个Adobe-GenP实用技巧:从安装到完美运行Photoshop

5个Adobe-GenP实用技巧&#xff1a;从安装到完美运行Photoshop 【免费下载链接】Adobe-GenP Adobe CC 2019/2020/2021/2022/2023 GenP Universal Patch 3.0 项目地址: https://gitcode.com/gh_mirrors/ad/Adobe-GenP Adobe-GenP是一款强大的Adobe Creative Cloud通用补丁…...

Switch模拟器Ryujinx全攻略:从安装到优化的跨平台游戏体验

Switch模拟器Ryujinx全攻略&#xff1a;从安装到优化的跨平台游戏体验 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx Switch模拟器Ryujinx是一款用C#编写的开源项目&#xff0c;它能让…...

对于对话中的对话状态跟踪,OpenClaw 的跨领域迁移能力?

在讨论对话状态跟踪这个问题时&#xff0c;OpenClaw 的跨领域迁移能力其实是一个挺有意思的切入点。很多人在初次接触这个概念时&#xff0c;可能会觉得这不过是另一个模型在多个数据集上跑出来的结果&#xff0c;但真正深入去看&#xff0c;会发现背后有不少值得琢磨的地方。 …...

Ostrakon-VL-8B实战:基于Transformer架构的视觉问答效果展示

Ostrakon-VL-8B实战&#xff1a;基于Transformer架构的视觉问答效果展示 最近在测试各种多模态模型时&#xff0c;我遇到了一个挺有意思的家伙——Ostrakon-VL-8B。这名字听起来有点拗口&#xff0c;但简单来说&#xff0c;它是一个拥有80亿参数的视觉语言模型&#xff0c;专门…...

零基础快速上手AI万能分类器:可视化文本分类系统部署

零基础快速上手AI万能分类器&#xff1a;可视化文本分类系统部署 1. 引言&#xff1a;什么是AI万能分类器&#xff1f; 想象一下&#xff0c;你手头有1000篇科研论文需要分类&#xff0c;传统方法可能需要你&#xff1a; 先定义好分类规则然后一篇篇阅读最后手动打上标签 这…...

手把手教你用SRIO IP核实现FPGA与DSP间高速数据互传:基于AXI-Stream接口的实战

基于SRIO IP核的FPGA与DSP高速数据互传实战指南 在异构计算系统中&#xff0c;FPGA与DSP的高效协同已成为雷达信号处理、无线通信基带处理等领域的核心技术需求。传统的数据传输方式如SPI、UART等已无法满足现代系统对带宽和实时性的严苛要求&#xff0c;而Serial RapidIO&…...