60 最长有效括号
最长有效括号
- 题目描述
- 题解1 DP+stack
- 题解2 stack
- 题解3 DP
- 题解4 左右指针
题目描述
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"示例 3:
输入:s = ""
输出:0
题解1 DP+stack
class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;stack<int> stk;vector<int> dp(st+1, 0);for(int i = 0; i < st; i++){if(s[i] == '('){stk.push(i);// 如果是左括号说明i位置不会有效,对应在dp里i+1位置置零即可dp[i+1] = 0;}else{if(! stk.empty()){// 如果没有stack,递推公式稍微复杂一点// key:别忘了+dp[stk.top()]// 以防迷惑:stk.top()是最近的左括号下标值,dp[stk.top()+1]=0dp[i+1] = i + 1 - stk.top() + dp[stk.top()];stk.pop(); }else dp[i+1] = 0;}}int ret = INT_MIN;for(auto& i : dp){ret = max(ret, i);}return ret;}
};

题解2 stack
class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;stack<int> stk;// 处理第一个字符是左括号的情况stk.push(-1);int ret = 0;for(int i = 0; i < st; i++){if(s[i] == '('){stk.push(i);}else{// 遇到右括号,先弹栈(遇到右括号,前面的连续有效括号就作废了)stk.pop();if(! stk.empty()){ret = max(ret, i-stk.top());}else {stk.push(i);}}}return ret;}
};

题解3 DP
class Solution {
public:int longestValidParentheses(string s) {int st = s.size();if(0 == st) return 0;vector<int> dp(st, 0);int maxS = 0; for(int i = 1; i < st; i++){if(s[i] == ')'){// "()()"if(s[i-1] == '('){dp[i] = 2;// 前面还有项(如果有stack就会马上定位到上一个有效序列的开始)if(i >= 2)dp[i] = dp[i-2] + dp[i];}// "(())"else if(dp[i-1]){if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '('){dp[i] = dp[i-1] + 2;// 前面还有项if(i - dp[i-1] - 2 >= 0)dp[i] = dp[i] + dp[i - dp[i - 1] - 2];} } }maxS = max(maxS, dp[i]);}return maxS;}
};

题解4 左右指针
class Solution {
public:int longestValidParentheses(string s) {int left = 0, right = 0, maxlength = 0;// 左扫for (int i = 0; i < s.length(); i++) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = max(maxlength, 2 * right);} else if (right > left) {left = right = 0;}}left = right = 0;// 右扫:解决左扫扫不出来的"(((()"for (int i = (int)s.length() - 1; i >= 0; i--) {if (s[i] == '(') {left++;} else {right++;}if (left == right) {maxlength = max(maxlength, 2 * left);} else if (left > right) {left = right = 0;}}return maxlength;}
};

相关文章:
60 最长有效括号
最长有效括号 题目描述题解1 DPstack题解2 stack题解3 DP题解4 左右指针 题目描述 给你一个只包含 ( 和 ) 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输入:s "(()" 输出࿱…...
第17章 MQ(二)
17.11 RabbitMQ如何保证消息的顺序性 难度:★★ 重点:★★★ 白话解析 其实RabbitMQ是一个先进先出的队列,只要消息进入到队列之后那肯定是顺序的,其实这道题问的点就是在消息进队列之前和出队列之后如何保证顺序性。 1、要保证消息进队列的顺序性实际只需要保证生产者只…...
AV1 视频编码标准资源
AV1 视频编码标准资源 A Progress Report: The Alliance for Open Media and the AV1 Codec Alliance for Open Media(开放媒体联盟/AV1官网) aomanalyzer AOM ANALYZER TEST CLIPS(测试视频) (Download each of the the CIF clips found there, in YUV4MPEG (y4m) format…...
pycharm远程连接miniconda完整过程,以及遇到的问题解决
问题1:no-zero exit code(126) env: ‘/home/user2/miniconda3/envs/ihan/bin/python3’: Too many levels of symbolic links Python interpreter process exited with a non-zero exit code 126 因为选择的新建导致太多软连接,先在服务器上建好虚拟环…...
leetcode:2678. 老人的数目(python3解法)
难度:简单 给你一个下标从 0 开始的字符串 details 。details 中每个元素都是一位乘客的信息,信息用长度为 15 的字符串表示,表示方式如下: 前十个字符是乘客的手机号码。接下来的一个字符是乘客的性别。接下来两个字符是乘客的年…...
【马蹄集】—— 概率论专题:第二类斯特林数
概率论专题:第二类斯特林数 目录 MT2224 矩阵乘法MT2231 越狱MT2232 找朋友MT2233 盒子与球MT2234 点餐 MT2224 矩阵乘法 难度:黄金 时间限制:5秒 占用内存:128M 题目描述 输入两个矩阵,第一个矩阵尺寸为 l…...
spring中基础核心接口总结
理解这几个接口,及其实现类就可以快速了解spring,具体的用法参考其他spring资料 1.BeanFactory最基础最核心的接口 重要的实现类有:XmlBeanFactory,以及ApplicationContext接口下的类 2.Resource接口,可以通用地访问文件资源 1)ClassPathResource:读取…...
最新Tuxera NTFS2024破解版mac读写NTFS磁盘工具
Tuxera NTFS for Mac是一款Mac系统NTFS磁盘读写软件。在系统默认状态下,MacOSX只能实现对NTFS的读取功能,Tuxera NTFS可以帮助MacOS 系统的电脑顺利实现对NTFS分区的读/写功能。Tuxera NTFS 2024完美兼容最新版本的MacOS 11 Big Sur,在M1芯片…...
【标准化封装 SOT系列 】 E SOT-89
〇、SOT-89 这个封装也比较常见,但并不易错。 一、E部分 SOT-89 参数 pin-pin 间距1.5mm body size 4.52.5 二、符合当前标准的典型举例 名称pin 数厂家 body DE矩形 (mm)SOT-894Mini-Circuits – PGA-102 — 4.39/4.62.29/2.59 上图 MiniCircuits 也称DF78…...
【建立单链表:头插法,尾插法;循环列表,带尾指针的循环链表合并(将Tb合并在Ta之后)】
文章目录 一、单链表的基本操作的实现1.建立单链表:头插法----元素插入在链表头部,也叫头插法。2.建立单链表:尾插法----元素插入在链表尾部,也叫尾插法。 二、线性表的链式表示和实现1.循环列表2.带尾指针的循环链表合并…...
图论+线性基高斯消元与主元:1019T2 / P4151
http://cplusoj.com/d/senior/p/SS231019B 相当于图上选一条链和一堆环 考虑dfs生成树。 则链是两条从根出发的链 环是每条返祖边组成的环 所以环和链的异或和可以求出来 链的放到线性基里 然后线性基通过高斯消元求主元(贪心思想,主元可以令那一位…...
Django REST Framework完整教程-RESTful规范-序列化和反序列数据-数据视图
文章目录 1.简介及安装2.案例模型2.1.创建模型2.2.安装mysql必要组件2.3.管理后台转中文2.4.启动后台 3.数据序列化4.RESTful规范4.1.协议、域名和版本4.2.uri(统一资源标识符)4.3.查增删改4.4.过滤信息(Filtering)4.5.状态码(Status Codes&a…...
float、double类型的转化和判断为零问题
1、将字符串转化为float、double 浮点数在内存中的存储机制和整形数据不同,有舍入误差,在计算机中用近似表示任意某个实数。具体来说,这个数由一个整数或定点数(即尾数)乘以某个基数(计算机中通常是2&…...
强大的虚拟机软件 VMware Fusion Pro 13中文最新 for mac
VMware Fusion Pro是一款虚拟化软件,它允许在Mac电脑上同时运行Windows和其他操作系统,而无需重启电脑,它采用了领先的虚拟化技术,能够保证在Mac电脑在同时运行多个操作系统时表现出极高的效率和稳定性。 VMware Fusion Pro具有以…...
SystemVerilog Assertions应用指南 Chapter1.37 使用局部变量的SVA
在序列或者属性的内部可以局部定义变量,而且可以对这种变量进行赋值。变量接着子序列放置,用逗号隔开。如果子序列匹配,那么变量赋值语句执行。每次序列被尝试匹配时,会产生变量的一个新的备份。 module cubed(enable1, a, aa, clk);input logic [7:0] a; input logic enable1,…...
Linux实现无需手动输入密码的自动化SSH身份验证
SSH密钥身份验证是一种安全的方式,使您能够在无需手动输入密码的情况下连接到远程服务器。以下是如何设置SSH密钥身份验证,以便您的脚本能够自动运行: 步骤 生成SSH密钥对: 在您的本地系统上生成SSH密钥对。如果您尚未生成,请使用…...
CSS 效果 圆形里一个文字居中
效果实现源码: 宽度,高度必须确认,且相等 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><style>.circlew {width: 45px;height: 45p…...
排序算法,冒泡排序算法及优化,选择排序SelectionSort,快速排序(递归-分区)
一、冒泡排序算法: 介绍: 冒泡排序(Bubble Sort)是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需…...
编写内联函数求解 2x²+4x+5的值,并用主函数调用该函数
动态内存分配可以根据实际需要在程序运行过程中动态地申请内存空间,这种内存空间的分配和释放是由程序员自己管理的,因此也被称为手动内存分配。 C++ 中,动态内存的分配和释放是通过 new 和 delete 操作符进行的。new 操作符用于在堆内存上为对象动态分配空间,dele…...
【Release】Photoshop ICO file format plug-in 3.0
【Introduction】 The Photoshop ICO plug-in is a file format plug-in developed for Photoshop, which allows Photoshop to directly read and write ICO format files. Because Photoshop has powerful pixel bitmap editing functions, it has many users and a good us…...
暗黑破坏神2存档编辑器实战指南:网页版高效修改方案深度剖析
暗黑破坏神2存档编辑器实战指南:网页版高效修改方案深度剖析 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 还在为暗黑破坏神2的角色养成而烦恼吗?想要体验不同职业的完美配装,却不愿花费数百…...
新手避坑指南:用Vulnhub DC-3靶场练习渗透测试时,我踩过的5个坑及解决方法
新手渗透测试实战:从DC-3靶场中汲取的5个关键教训 初识DC-3靶场的挑战 当我第一次接触Vulnhub的DC-3靶机时,那种既兴奋又忐忑的心情至今记忆犹新。作为一个刚踏入渗透测试领域的新手,我原以为按照教程步骤就能轻松通关,但现实却给…...
从认证题看实战:金蝶云苍穹插件开发与事件机制深度解析
金蝶云苍穹插件开发与事件机制实战解析:从认证题到高阶应用 在当今企业数字化转型浪潮中,金蝶云苍穹作为新一代企业级PaaS平台,其插件开发能力已成为开发者必须掌握的核心技能。本文将以认证题为切入点,深入剖析苍穹平台的插件体系…...
终极NCM解密指南:3分钟解锁网易云音乐加密文件,实现跨设备自由播放
终极NCM解密指南:3分钟解锁网易云音乐加密文件,实现跨设备自由播放 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 还在为网易云音乐下载的NCM格式文件无法在其他设备播放而烦恼吗?ncmdump解密工具…...
告别Root后迷茫:手把手教你用Magisk模块激活LSPosed(Riru/Zygisk双版本保姆级教程)
从Root到模块实战:Magisk与LSPosed的终极配置指南 当你成功解锁Bootloader并完成Root后,真正的Android定制之旅才刚刚开始。面对琳琅满目的Magisk模块,特别是功能强大的LSPosed框架,许多用户会陷入选择困难——Riru还是Zygisk&am…...
别再手动巡检了!用Prometheus+vmware_exporter自动监控你的VMware vSphere集群(附K8s/Docker两种部署)
从人工巡检到智能告警:构建VMware vSphere全栈监控体系的实战指南 凌晨三点,刺耳的电话铃声划破夜空——某台关键业务虚拟机CPU负载飙升至98%,而值班工程师手忙脚乱地远程连接、收集日志、排查问题。这样的场景在传统运维模式下每周都会上演&…...
基于LangChain构建AI社交媒体智能体:自动化内容发布与互动实践
1. 项目概述:一个能帮你打理社交媒体的AI智能体最近在GitHub上看到一个挺有意思的项目,叫langchain-ai/social-media-agent。光看名字,你大概就能猜到它的核心功能:一个基于LangChain框架构建的、能够自动化处理社交媒体任务的AI智…...
清雪车远程监控运维管理系统方案
在北方某高速路段冬季除雪保畅作业中,现场配置了配备滚刷、雪铲、破冰装置及融雪剂撒布系统的多功能清雪车车队。管理层面临着车辆位置分布不清、作业状态无法实时感知的双重痛点。因此,车队打造信息化车辆管理平台的核心需求是:不仅要实时掌…...
基于卷积神经网络的球罐结构损伤识别
基于卷积神经网络的球罐结构损伤识别 摘要:球形储罐(球罐)作为储存各类气体和液化气体的核心压力容器,广泛应用于石油、化工、冶金及城市燃气供应等领域,其结构安全直接关系到人员生命和财产安全。传统无损检测方法存在效率低、范围有限、对微小损伤敏感度低等问题,难以…...
别再盲目memcpy!嵌入式C中模型权重加载的4种内存对齐误用,已致3起量产固件崩溃
更多请点击: https://intelliparadigm.com 第一章:嵌入式C中模型权重加载的内存对齐本质与危害全景 内存对齐的本质:硬件访问契约 在ARM Cortex-M系列或RISC-V嵌入式平台中,CPU对非对齐地址执行32位读写会触发硬故障(…...
