建设一个收入支出持平的网站,网络推广计划书格式,sae wordpress 主题 下载,中国建设信息网官网八大员证查询最长有效括号 题目描述题解1 DPstack题解2 stack题解3 DP题解4 左右指针 题目描述
给你一个只包含 ( 和 ) 的字符串#xff0c;找出最长有效#xff08;格式正确且连续#xff09;括号子串的长度。
示例 1#xff1a;
输入#xff1a;s (()
输出#xff1… 最长有效括号 题目描述题解1 DPstack题解2 stack题解3 DP题解4 左右指针 题目描述
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
示例 1
输入s (()
输出2
解释最长有效括号子串是 ()示例 2
输入s )()())
输出4
解释最长有效括号子串是 ()()示例 3
输入s
输出0题解1 DPstack
class Solution {
public:int longestValidParentheses(string s) {int st s.size();if(0 st) return 0;stackint stk;vectorint dp(st1, 0);for(int i 0; i st; i){if(s[i] (){stk.push(i);// 如果是左括号说明i位置不会有效对应在dp里i1位置置零即可dp[i1] 0;}else{if(! stk.empty()){// 如果没有stack递推公式稍微复杂一点// key别忘了dp[stk.top()]// 以防迷惑stk.top()是最近的左括号下标值dp[stk.top()1]0dp[i1] i 1 - stk.top() dp[stk.top()];stk.pop(); }else dp[i1] 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;stackint 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;vectorint 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;}
};
