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

Leetcode热题100-32 最长有效括号

Leetcode热题100-32 最长有效括号

  • 1. 题目描述
  • 2. 解题思路
    • 动态规划
    • 栈解法
  • 3. 代码实现
    • 动态规划
    • 栈解法

1. 题目描述

32 最长有效括号

2. 解题思路

动态规划

定义状态:

  • dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。

状态转移方程:
遍历字符串 s,当遇到 s[i] == ')' 时,存在以下两种情况:

  1. 情况 1:s[i - 1] == '('
    • 当前字符 ')' 与前一个字符 '(' 组成了一对匹配的括号。
    • 更新状态:
      d p [ i ] = ( i ≥ 2 ? d p [ i − 2 ] : 0 ) + 2 dp[i] = (i \geq 2 ? dp[i - 2] : 0) + 2 dp[i]=(i2?dp[i2]:0)+2
  2. 情况 2:s[i - 1] == ')'
    • 需要满足条件:i - dp[i - 1] > 0,即前面存在可以与当前 ')' 匹配的 '('
      d p [ i ] = ( i − d p [ i − 1 ] ≥ 2 ? d p [ i − d p [ i − 1 ] − 2 ] : 0 ) + d p [ i − 1 ] + 2 dp[i] = (i - dp[i - 1] \geq 2 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2 dp[i]=(idp[i1]2?dp[idp[i1]2]:0)+dp[i1]+2
    • 其中:
      • dp[i - dp[i - 1] - 2] 表示与当前匹配的 '(' 前面的有效子串长度(若存在,否则为 0)。
      • dp[i - 1] 是前一个位置的最长有效子串长度。
      • s[i - dp[i - 1] - 1]s[i] 匹配(长度为 2)。

更新最大值:
在遍历过程中,更新最大长度:
maxLen = max ⁡ ( maxLen , d p [ i ] ) \text{{maxLen}} = \max(\text{{maxLen}}, dp[i]) maxLen=max(maxLen,dp[i])
遍历结束后,maxLen 即为所求结果。

栈解法

初始化:

  • 使用一个栈 stk 存储索引。
  • -1 压入栈,表示最后一个未匹配的右括号的索引。

遍历字符串:

  • 遍历字符串中的每个字符:
    1. 如果当前字符为 '(',将其索引压入栈。
    2. 如果当前字符为 ')'
      • 弹出栈顶元素,表示尝试匹配最近的 '('
      • 如果栈为空,说明没有匹配的 '(',将当前索引压入栈。
      • 如果栈不为空,计算当前有效括号的长度,并更新最大长度 maxLen
        maxLen = max ⁡ ( maxLen , i − stack.top() ) \text{{maxLen}} = \max(\text{{maxLen}}, i - \text{{stack.top()}}) maxLen=max(maxLen,istack.top())

3. 代码实现

动态规划

class Solution {
public:// 使用栈来解决问题int longestValidParentheses(string s) {int maxLen = 0;int n = s.size();vector<int> dp(n, 0);// 注意到子串是指字符串中连续的字符序列for (int i = 1; i < n; i++) {if (s[i] == ')') {// 直接匹配if (s[i - 1] == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;}// s[i-1]=')'else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {// dp[i-dp[i-1]-2]表示与dp[i-1]相连的有效子字符串的长度// dp[i]由三部分组成// s[i-dp[i-1]-1]与s[i]匹配(长度为2)// dp[i - 1]// dp[i - dp[i - 1] - 2]或者为0dp[i] = (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) +dp[i - 1] + 2;}}maxLen = max(maxLen, dp[i]);}return maxLen;}
};

栈解法

class Solution {
public:int longestValidParentheses(string s) {int res=0;stack<int> stk;stk.push(-1);for(int i=0;i<s.size();i++){if(s[i]=='('){stk.push(i);}else{stk.pop();if(stk.empty()){stk.push(i);}else{res=max(res,i-stk.top());}}}return res;}
};

相关文章:

Leetcode热题100-32 最长有效括号

Leetcode热题100-32 最长有效括号 1. 题目描述2. 解题思路动态规划栈解法 3. 代码实现动态规划栈解法 1. 题目描述 32 最长有效括号 2. 解题思路 动态规划 定义状态&#xff1a; 设 dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。 状态转移方程&#xff1a; 遍历字符…...

【大数据学习 | HBASE】hbase的读数据流程与hbase读取数据

1. hbase的读数据流程 在解析读取流程之前我们还需要知道两个功能性的组件和HFIle的格式信息 HFILE 存储在hdfs中的hbase文件&#xff0c;这个文件中会存在hbase中的数据以kv类型显示&#xff0c;同时还会存在hbase的元数据信息&#xff0c;包括整个hfile文件的索引大小&…...

A027-基于Spring Boot的农事管理系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…...

Redisson的可重入锁

初始状态&#xff1a; 表示系统或资源在没有线程持有锁的情况下的状态&#xff0c;任何线程都可以尝试获取锁。 线程 1 获得锁&#xff1a; 线程 1 首次获取了锁并进入受保护的代码区域。 线程 1 再次请求锁&#xff1a; 在持有锁的情况下&#xff0c;线程 1 再次请求锁&a…...

SQL Server Service Broker完整示例

目录 准备 创建Message&#xff0c;Contract&#xff0c;Queue和Service 创建调用存储过程 启用SQL Agent并创建Job执行存储过程 调用demo 常见故障排除 准备 判断你的数据库YourDatabaseName是否启用了Service Broker SELECT is_broker_enabled FROM sys.databases WH…...

CentOS7 升级OpenSSH9.0全过程和坑

近日,漏洞肆虐,需要升级新版本,才能解决漏洞。故有此文: 0 查看当前版本 [root@host-testsvc openssh-9.0p1]# ssh -V OpenSSH_7.4p1, OpenSSL 1.0.2k-fips 26 Jan 20171、在data下新建一个独立目录openssh目录,用来存放软件 [root@host-testsvc data]# mkdir openssh…...

RSTP的配置

RSTP相对于STP在端口角色、端口状态、配置BPDU格式、配置BPDU的处理方式、快速收敛机制、拓扑变更机制和4种保护特性方面的详细改进说明&#xff1a; 端口角色&#xff1a; STP中定义了三种端口角色&#xff1a;根端口&#xff08;Root Port&#xff09;、指定端口&#xff0…...

力扣257:二叉树的所有路径

给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [1,2,3,null,5] 输出&#xff1a;["1->2->5","1->3"]示例…...

Tcl 和 Python 在二次开发研究

引言 Tcl(Tool Command Language)和 Python 都是广泛应用于各种领域的编程语言,特别是在二次开发和自动化开发方面,两者有着独特的特性。Tcl 是一种动态的脚本语言,早期主要用于集成和控制其他程序,因此它经常出现在嵌入式应用和图形用户界面(GUI)开发中。而 Python 是…...

【NLP优化】Ubuntu 20.04 下 源码安装 CasADi + Ipopt / acados

20241114 记录一下 Ubuntu 20.04 下安装 MPC 中两种常用开源 NLP 优化器 CasADi + Ipopt / acados 可以新建一个文件夹,保存所有源码安装下载的代码 mkdir ~/mpc_dep1. 安装依赖 # **IPOPT** sudo apt-get install gcc g++ gfortran git patch wget pkg-config libmetis-de…...

[241110] 微软发布多智能体系统Magentic-One | 社区讨论:Ubuntu 26.04 LTS 发布前移除 Qt 5

目录 微软发布多智能体系统 Magentic-One社区讨论&#xff1a;Ubuntu 26.04 LTS 发布前移除 Qt 5 微软发布多智能体系统 Magentic-One 微软研究院近日发布了一个名为 Magentic-One 的多智能体系统&#xff0c;旨在解决复杂的现实世界任务。这个系统展现了令人兴奋的潜力&#…...

AI风向标|算力与通信的完美融合,SRM6690解锁端侧AI的智能密码

当前&#xff0c;5G技术已经成为推动数字经济和实体经济深度融合的关键驱动力&#xff0c;进入5G发展的下半场&#xff0c;5G与AI的融合正推动诸多行业的数字化转型和创新发展&#xff0c;终端侧AI和端云混合式AI将广泛应用于各类消费终端和各行各业。 在推动5G和AI与各行业场…...

MySQL查询执行(六):join查询

到底可不可以使用join 假设存在如下表结构&#xff1a; -- 创建表t2 CREATE TABLE t2 (id int(11) NOT NULL,a int(11) DEFAULT NULL,b int(11) DEFAULT NULL,PRIMARY KEY (id),KEY a (a) ) ENGINEInnoDB;-- 向t2写入1000条数据 drop procedure idata; delimiter ;; create pr…...

python习题练习

python习题 编写一个简单的工资管理程序系统可以管理以下四类人:工人(worker)、销售员(salesman)、经理(manager)、销售经理(salemanger)所有的员工都具有员工号&#xff0c;工资等属性&#xff0c;有设置姓名&#xff0c;获取姓名&#xff0c;获取员工号&#xff0c;计算工资等…...

MySQL高级(二):一条更新语句是如何执行的

执行步骤 1. 解析 SQL 语句 MySQL 首先会解析你输入的 UPDATE 语句。解析器会检查语法是否正确&#xff0c;并将 SQL 语句转化为内部的数据结构&#xff08;通常是语法树&#xff09;。 示例 SQL 语句&#xff1a; UPDATE employees SET salary 5000 WHERE department Sa…...

在 Ubuntu 18.04 中搭建和测试 DNS 服务器

在 Ubuntu 18.04 中搭建和测试 DNS 服务器可以通过安装和配置 BIND&#xff08;Berkeley Internet Name Domain&#xff09;来实现。以下是详细的步骤&#xff1a; 1. 安装 BIND 打开终端并运行以下命令来安装 BIND&#xff1a; sudo apt update sudo apt install bind9 bin…...

算法学习第一弹——C++基础

早上好啊&#xff0c;大佬们。来看看咱们这回学点啥&#xff0c;在前不久刚出完C语言写的PTA中L1的题目&#xff0c;想必大家都不过瘾&#xff0c;感觉那些题都不过如此&#xff0c;所以&#xff0c;为了我们能更好的去处理更难的题目&#xff0c;小白兔决定奋发图强&#xff0…...

javaWeb小白项目--学生宿舍管理系统

目录 一、检查并关闭占用端口的进程 二、修改 Tomcat 的端口配置 三、重新启动 Tomcat 一、javaw.exe的作用 二、结束javaw.exe任务的影响 三、如何判断是否可以结束 结尾&#xff1a; 这个错误提示表明在本地启动 Tomcat v9.0 服务器时遇到了问题&#xff0c;原因是所需…...

如何优化Elasticsearch的查询性能?

优化Elasticsearch查询性能可以从以下几个方面进行&#xff1a; 合理设计索引和分片&#xff1a; 确保设置合理的分片和副本数&#xff0c;考虑数据量、节点数和集群大小。根据数据量和节点数量调整分片数量&#xff0c;避免使用过多分片&#xff0c;因为每个分片都需要额外的…...

蓝桥杯每日真题 - 第12天

题目&#xff1a;&#xff08;数三角&#xff09; 题目描述&#xff08;14届 C&C B组E题&#xff09; 解题思路&#xff1a; 给定 n 个点的坐标&#xff0c;计算其中可以组成 等腰三角形 的三点组合数量。 核心条件&#xff1a;等腰三角形的定义是三角形的三条边中至少有…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...