Leetcode热题100-32 最长有效括号
Leetcode热题100-32 最长有效括号
- 1. 题目描述
- 2. 解题思路
- 动态规划
- 栈解法
- 3. 代码实现
- 动态规划
- 栈解法
1. 题目描述
32 最长有效括号
2. 解题思路
动态规划
定义状态:
- 设
dp[i]表示以位置i结尾的最长有效括号子串的长度。
状态转移方程:
遍历字符串 s,当遇到 s[i] == ')' 时,存在以下两种情况:
- 情况 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]=(i≥2?dp[i−2]:0)+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]=(i−dp[i−1]≥2?dp[i−dp[i−1]−2]:0)+dp[i−1]+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压入栈,表示最后一个未匹配的右括号的索引。
遍历字符串:
- 遍历字符串中的每个字符:
- 如果当前字符为
'(',将其索引压入栈。 - 如果当前字符为
')':- 弹出栈顶元素,表示尝试匹配最近的
'('。 - 如果栈为空,说明没有匹配的
'(',将当前索引压入栈。 - 如果栈不为空,计算当前有效括号的长度,并更新最大长度
maxLen:
maxLen = max ( maxLen , i − stack.top() ) \text{{maxLen}} = \max(\text{{maxLen}}, i - \text{{stack.top()}}) maxLen=max(maxLen,i−stack.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. 解题思路 动态规划 定义状态: 设 dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。 状态转移方程: 遍历字符…...
【大数据学习 | HBASE】hbase的读数据流程与hbase读取数据
1. hbase的读数据流程 在解析读取流程之前我们还需要知道两个功能性的组件和HFIle的格式信息 HFILE 存储在hdfs中的hbase文件,这个文件中会存在hbase中的数据以kv类型显示,同时还会存在hbase的元数据信息,包括整个hfile文件的索引大小&…...
A027-基于Spring Boot的农事管理系统
🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…...
Redisson的可重入锁
初始状态: 表示系统或资源在没有线程持有锁的情况下的状态,任何线程都可以尝试获取锁。 线程 1 获得锁: 线程 1 首次获取了锁并进入受保护的代码区域。 线程 1 再次请求锁: 在持有锁的情况下,线程 1 再次请求锁&a…...
SQL Server Service Broker完整示例
目录 准备 创建Message,Contract,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种保护特性方面的详细改进说明: 端口角色: STP中定义了三种端口角色:根端口(Root Port)、指定端口࿰…...
力扣257:二叉树的所有路径
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root [1,2,3,null,5] 输出:["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社区讨论:Ubuntu 26.04 LTS 发布前移除 Qt 5 微软发布多智能体系统 Magentic-One 微软研究院近日发布了一个名为 Magentic-One 的多智能体系统,旨在解决复杂的现实世界任务。这个系统展现了令人兴奋的潜力&#…...
AI风向标|算力与通信的完美融合,SRM6690解锁端侧AI的智能密码
当前,5G技术已经成为推动数字经济和实体经济深度融合的关键驱动力,进入5G发展的下半场,5G与AI的融合正推动诸多行业的数字化转型和创新发展,终端侧AI和端云混合式AI将广泛应用于各类消费终端和各行各业。 在推动5G和AI与各行业场…...
MySQL查询执行(六):join查询
到底可不可以使用join 假设存在如下表结构: -- 创建表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)所有的员工都具有员工号,工资等属性,有设置姓名,获取姓名,获取员工号,计算工资等…...
MySQL高级(二):一条更新语句是如何执行的
执行步骤 1. 解析 SQL 语句 MySQL 首先会解析你输入的 UPDATE 语句。解析器会检查语法是否正确,并将 SQL 语句转化为内部的数据结构(通常是语法树)。 示例 SQL 语句: UPDATE employees SET salary 5000 WHERE department Sa…...
在 Ubuntu 18.04 中搭建和测试 DNS 服务器
在 Ubuntu 18.04 中搭建和测试 DNS 服务器可以通过安装和配置 BIND(Berkeley Internet Name Domain)来实现。以下是详细的步骤: 1. 安装 BIND 打开终端并运行以下命令来安装 BIND: sudo apt update sudo apt install bind9 bin…...
算法学习第一弹——C++基础
早上好啊,大佬们。来看看咱们这回学点啥,在前不久刚出完C语言写的PTA中L1的题目,想必大家都不过瘾,感觉那些题都不过如此,所以,为了我们能更好的去处理更难的题目,小白兔决定奋发图强࿰…...
javaWeb小白项目--学生宿舍管理系统
目录 一、检查并关闭占用端口的进程 二、修改 Tomcat 的端口配置 三、重新启动 Tomcat 一、javaw.exe的作用 二、结束javaw.exe任务的影响 三、如何判断是否可以结束 结尾: 这个错误提示表明在本地启动 Tomcat v9.0 服务器时遇到了问题,原因是所需…...
如何优化Elasticsearch的查询性能?
优化Elasticsearch查询性能可以从以下几个方面进行: 合理设计索引和分片: 确保设置合理的分片和副本数,考虑数据量、节点数和集群大小。根据数据量和节点数量调整分片数量,避免使用过多分片,因为每个分片都需要额外的…...
蓝桥杯每日真题 - 第12天
题目:(数三角) 题目描述(14届 C&C B组E题) 解题思路: 给定 n 个点的坐标,计算其中可以组成 等腰三角形 的三点组合数量。 核心条件:等腰三角形的定义是三角形的三条边中至少有…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
