当前位置:网站首页>【力扣刷题】32. 最长有效括号
【力扣刷题】32. 最长有效括号
2022-07-06 12:56:00 【李小恩恩子】
目录
方法一:
题目:
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
方法一:
解题思路:
利用栈,学过利用栈来判断一个只包含'('和')'的字符串是否是括号匹配的,那个题目解题就是,遍历整个字符串,是左括号就入栈,是右括号则①判断栈是否有左括号且弹出一个左括号,②如果栈为空则为false,如果所有字符都遍历完了,栈中还有元素则为false,否则为true。
利用这个思路,增加一个标记数组arr,初始化所有元素为1,栈中存的是数组下标(字符索引)。遍历整个字符串,如果是左括号则把索引下标(i)加入栈,如果是右括号则判断栈中元素是否为空且不为空则弹出,并把标记数组对应的元素arr[stack.pop()]以及当前下标对应的标记数组元素arr[i]置为0。
最后判断标记数组arr的最长连续0就可以了。
代码:
class Solution {
public int longestValidParentheses(String s) {
//要找最长的有效括号
//栈
//利用栈来标记左右括号是否有效,栈的内容存下标i
Stack<Integer> stack = new Stack<>();
int[] valid = new int[s.length()];
for(int i = 0; i < s.length(); i++){
valid[i] = 1;
}
for(int i = 0; i < s.length();i++){
if(s.charAt(i) == '(') stack.push(i);
else{
if(!stack.empty()){
valid[i] = 0;
valid[stack.pop()] = 0;
}
}
}
int res = 0,count = 0;
for(int i = 0; i < s.length();i++){
if(valid[i] == 1) {
count = 0;
}else{
count++;
}
res = Math.max(res,count);
}
return res;
}
}
方法二:
解题思路:
动态规划,利用dp[i]表示以下标i字符结尾的最长有效括号的长度。将dp数组全部初始化为0。有效的子串一定以')'结尾,以'('结尾的子串对应的dp值必定为0。所以只需要求解以')'在dp数组中对应位置的值。所以从前往后遍历字符串,求解dp值。
①s.charAt(i)=')'且s.charAt(i-1)='(',字符串为"...()"则dp[i] = dp[i-2]+2。
②如果s.charAt(i) = ')'且s.charAt(i-1) = ')',比如字符串"...))"->"()(())",
如果s.charAt(i - dp[i - 1] - 1)='(',那么有效括号长度新增长度2,i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2,不过得注意,i − dp[i − 1] − 1 和 i 组成了有效括号对,这将是一段独立的有效括号序列,如果之前的子序列是形如 (...)(...) 这种序列,那么当前位置的最长有效括号长度还需要加上这一段。例如:()(()),左边红色的和右边绿色的为两个独立的有效括号序列。所以状态转移方程为:dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] -2 ]。
图示:
还要注意边界值,因为要用到 dp[ i - 2 ],还有dp[ i - dp[ i - 1 ] - 2 ],要判断。
代码:
class Solution {
public int longestValidParentheses(String s) {
//动态规划
//dp[i]表示以下标i字符结尾的最长有效括号的长度
int res = 0;
int[] dp = new int[s.length()];
for(int i = 1;i < s.length();i++){
if(s.charAt(i) == ')'){
if(s.charAt(i-1) == '('){
if(i >= 2) dp[i] = dp[i - 2] + 2;
else dp[i] = 2;
}else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
if(i - dp[i - 1] >= 2) dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
else dp[i] = dp[i - 1] + 2;
}
}
res = Math.max(res,dp[i]);
}
return res;
}
}
方法二看了看解析,不太会写动态规划,下次找个机会专门练一练动态规划的题目。
边栏推荐
- 基于STM32单片机设计的红外测温仪(带人脸检测)
- What's the best way to get TFS to output each project to its own directory?
- 面试官:Redis中有序集合的内部实现方式是什么?
- 拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条
- 每个程序员必须掌握的常用英语词汇(建议收藏)
- The biggest pain point of traffic management - the resource utilization rate cannot go up
- Forward maximum matching method
- 3D人脸重建:从基础知识到识别/重建方法!
- SAP Fiori应用索引大全工具和 SAP Fiori Tools 的使用介绍
- Swagger UI tutorial API document artifact
猜你喜欢
ICML 2022 | Flowformer: 任务通用的线性复杂度Transformer
[MySQL] trigger
After working for 5 years, this experience is left when you reach P7. You have helped your friends get 10 offers
Opencv learning example code 3.2.3 image binarization
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条
【mysql】触发器
The most comprehensive new database in the whole network, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, flying Book Multidimensional table, heipayun, Zhix
Manifest of SAP ui5 framework json
Introduction to the use of SAP Fiori application index tool and SAP Fiori tools
2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
随机推荐
基于深度学习的参考帧生成
【Redis设计与实现】第一部分 :Redis数据结构和对象 总结
嵌入式开发的7大原罪
No Yum source to install SPuG monitoring
全网最全的知识库管理工具综合评测和推荐:FlowUs、Baklib、简道云、ONES Wiki 、PingCode、Seed、MeBox、亿方云、智米云、搜阅云、天翎
Reviewer dis's whole research direction is not just reviewing my manuscript. What should I do?
2022菲尔兹奖揭晓!首位韩裔许埈珥上榜,四位80后得奖,乌克兰女数学家成史上唯二获奖女性
Variable star --- article module (1)
Word bag model and TF-IDF
3D人脸重建:从基础知识到识别/重建方法!
Can novices speculate in stocks for 200 yuan? Is the securities account given by qiniu safe?
Manifest of SAP ui5 framework json
Forward maximum matching method
js 根据汉字首字母排序(省份排序) 或 根据英文首字母排序——za排序 & az排序
Reference frame generation based on deep learning
代理和反向代理
Pat 1078 hashing (25 points) ⼆ times ⽅ exploration method
What is the difference between procedural SQL and C language in defining variables
Thinking about agile development
Performance test process and plan