当前位置:网站首页>[Li Kou brush questions] 32 Longest valid bracket
[Li Kou brush questions] 32 Longest valid bracket
2022-07-06 21:20:00 【Li xiaoenzi】
Catalog
Method 1 :
subject :
Give you one that only contains '('
and ')'
String , Find the longest effective ( The format is correct and continuous ) The length of the bracket substring .
Method 1 :
Their thinking :
Utilization stack , I learned to use the stack to judge that a contains only '(' and ')' Whether the string of is parenthesized , The solution to that problem is , Traversing the entire string , If it's an open parenthesis, it's on the stack , Is the right parenthesis ① Determine whether the stack has an open bracket and pop up an open bracket ,② If the stack is empty, then false, If all characters are traversed , If there are elements in the stack, they are false, Otherwise true.
Use this idea , Add an array of tags arr, Initialize all elements to 1, What is stored in the stack is the array subscript ( Character index ). Traversing the entire string , If it is an open parenthesis, the index subscript (i) Join the stack , If it is a right parenthesis, judge whether the element in the stack is empty and if not, pop up , And mark the elements corresponding to the array arr[stack.pop()] And the tag array element corresponding to the current subscript arr[i] Set as 0.
Finally, determine the tag array arr The longest continuous 0 That's all right. .
Code :
class Solution {
public int longestValidParentheses(String s) {
// Find the longest valid bracket
// Stack
// Use the stack to mark whether the left and right parentheses are valid , The contents of the stack are stored with subscripts 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;
}
}
Method 2 :
Their thinking :
Dynamic programming , utilize dp[i] Express By subscript i The length of the longest valid bracket at the end of the character . take dp The array is all initialized to 0. A valid substring must be in ')' ending , With '(' The ending substring corresponds to dp The value must be 0. So we just need to solve it to ')' stay dp The value of the corresponding position in the array . So go through the string from front to back , solve dp value .
①s.charAt(i)=')' And s.charAt(i-1)='(', String is "...()" be dp[i] = dp[i-2]+2.
② If s.charAt(i) = ')' And s.charAt(i-1) = ')', Like strings "...))"->"()(())",
If s.charAt(i - dp[i - 1] - 1)='(', Then the effective bracket length increases the length 2,i The longest valid bracket length of position pair is i-1 The longest bracket length of the position plus the new 2, But you have to Be careful ,i − dp[i − 1] − 1 and i Form a valid pair of parentheses , This will be a paragraph Independent valid parenthesis sequence , If the previous subsequence is shaped like (...)(...) This sequence , Then the longest valid bracket length of the current position needs to add this paragraph . for example :()(()), The red one on the left and The green one on the right Is a sequence of two independent valid parentheses . So the state transfer equation is :dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] -2 ].
Icon :
Also note the boundary value , Because we need to use it dp[ i - 2 ], also dp[ i - dp[ i - 1 ] - 2 ], To judge .
Code :
class Solution {
public int longestValidParentheses(String s) {
// Dynamic programming
//dp[i] Denotes the following i The length of the longest valid bracket at the end of the character
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;
}
}
Method 2: look at the analysis , Not good at writing Dynamic Planning , Next time, find an opportunity to practice the topic of Dynamic Planning .
边栏推荐
- document.write()的用法-写入文本——修改样式、位置控制
- What are RDB and AOF
- 启动嵌入式间:资源有限的系统启动
- Le langage r visualise les relations entre plus de deux variables de classification (catégories), crée des plots Mosaiques en utilisant la fonction Mosaic dans le paquet VCD, et visualise les relation
- 【滑动窗口】第九届蓝桥杯省赛B组:日志统计
- OneNote in-depth evaluation: using resources, plug-ins, templates
- 技术分享 | 抓包分析 TCP 协议
- [interpretation of the paper] machine learning technology for Cataract Classification / classification
- C # use Oracle stored procedure to obtain result set instance
- 【Redis设计与实现】第一部分 :Redis数据结构和对象 总结
猜你喜欢
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
[interpretation of the paper] machine learning technology for Cataract Classification / classification
每个程序员必须掌握的常用英语词汇(建议收藏)
Reviewer dis's whole research direction is not just reviewing my manuscript. What should I do?
跨分片方案 总结
Aike AI frontier promotion (7.6)
The difference between break and continue in the for loop -- break completely end the loop & continue terminate this loop
Why do job hopping take more than promotion?
SAP Fiori应用索引大全工具和 SAP Fiori Tools 的使用介绍
【论文解读】用于白内障分级/分类的机器学习技术
随机推荐
【Redis设计与实现】第一部分 :Redis数据结构和对象 总结
PHP saves session data to MySQL database
监控界的最强王者,没有之一!
VIM basic configuration and frequently used commands
None of the strongest kings in the monitoring industry!
The biggest pain point of traffic management - the resource utilization rate cannot go up
Divide candy
爱可可AI前沿推介(7.6)
Start the embedded room: system startup with limited resources
SDL2来源分析7:演出(SDL_RenderPresent())
@PathVariable
js之遍历数组、字符串
Set up a time server
document. Usage of write () - write text - modify style and position control
Infrared thermometer based on STM32 single chip microcomputer (with face detection)
'class file has wrong version 52.0, should be 50.0' - class file has wrong version 52.0, should be 50.0
el-table表格——获取单击的是第几行和第几列 & 表格排序之el-table与sort-change、el-table-column与sort-method & 清除排序-clearSort
[interpretation of the paper] machine learning technology for Cataract Classification / classification
15million employees are easy to manage, and the cloud native database gaussdb makes HR office more efficient
技术分享 | 抓包分析 TCP 协议