深圳营销型网站建设+宝安西乡,网站开发包括网站的等过程,网站站长如何赚钱,酒店网站建设特色题目
给你一个只包含 ‘(’ 和 ‘)’ 的字符串 s s s#xff0c;找出最长有效#xff08;格式正确且连续#xff09;括号子串的长度。
方法
动态规划 d p [ i ] dp[i] dp[i] 表示以 s [ i ] s[i] s[i] 结尾的最长有效括号的长度如果 s [ i ] s[i] s[i] 为左括号#…题目
给你一个只包含 ‘(’ 和 ‘)’ 的字符串 s s s找出最长有效格式正确且连续括号子串的长度。
方法
动态规划 d p [ i ] dp[i] dp[i] 表示以 s [ i ] s[i] s[i] 结尾的最长有效括号的长度如果 s [ i ] s[i] s[i] 为左括号则 d p [ i ] 0 dp[i] 0 dp[i]0如果 s [ i ] s[i] s[i] 为右括号 若 s [ i − 1 ] s[i-1] s[i−1] 为左括号 则 d p [ i ] d p [ i − 2 ] 2 dp[i] dp[i-2] 2 dp[i]dp[i−2]2若 s [ i − 1 ] s[i-1] s[i−1] 为右括号 若 s [ i − 1 − d p [ i − 1 ] ] s[i-1-dp[i-1]] s[i−1−dp[i−1]] 为左括号则 d p [ i ] d p [ i − 1 ] d p [ i − 2 − d p [ i − 1 ] ] 2 dp[i] dp[i-1] dp[i-2-dp[i-1]] 2 dp[i]dp[i−1]dp[i−2−dp[i−1]]2若 s [ i − 1 − d p [ i − 1 ] ] s[i-1-dp[i-1]] s[i−1−dp[i−1]] 为右括号则 d p [ i ] 0 dp[i] 0 dp[i]0
栈 始终保持栈底元素为最后一个没有被匹配的右括号的下标这样的做法主要是考虑了边界条件的处理栈里其他元素维护左括号的下标 对于遇到的每个‘(’ 我们将它的下标放入栈中对于遇到的每个‘)’我们先弹出栈顶元素表示匹配了当前右括号 如果栈为空说明当前的右括号为没有被匹配的右括号我们将其下标放入栈中来更新我们之前提到最后一个没有被匹配的右括号的下标如果栈不为空当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度 我们从前往后遍历字符串并更新答案即可。 需要注意的是如果一开始栈为空第一个字符为左括号的时候我们会将其放入栈中这样就不满足提及的最后一个没有被匹配的右括号的下标为了保持统一我们在一开始的时候往栈中放入一个值为 − 1 -1 −1 的元素
两次遍历
从左往右遍历字符串 当遇到左括号时 l e f t left left 加一当遇到右括号时 r i g h t right right 加一当 l e f t r i g h t left right leftright更新一次最长有效括号的长度当 l e f t r i g h t left right leftright将两个变量清零 从右往左遍历字符串 当遇到左括号时 l e f t left left 加一当遇到右括号时 r i g h t right right 加一当 l e f t r i g h t left right leftright更新一次最长有效括号的长度当 l e f t r i g h t left right leftright将两个变量清零
代码
class Solution {
public:int longestValidParentheses(string s) {// int n s.size();// stackint stk;// vectorvectorint ind_list;// stk.push(-1);// int ret 0;// for(int i 0; i n; i){// if(s[i] (){// stk.push(i);// }// else{// if(stk.top() ! -1){// if(ind_list.size()0 stk.top()-ind_list[ind_list.size()-1][1] 0){// ind_list[ind_list.size()-1][0] stk.top();// ind_list[ind_list.size()-1][1] i;// }// else// ind_list.push_back({stk.top(), i});// if(ind_list.size()2){// int r1 ind_list[ind_list.size()-2][1];// int l2 ind_list[ind_list.size()-1][0];// int r2 ind_list[ind_list.size()-1][1];// if(l2-r1 1){// ind_list[ind_list.size()-2][1] r2;// ind_list.pop_back();// }// }// stk.pop();// }// }// }// for(int i 0; i ind_list.size(); i){// ret max(ret, ind_list[i][1]-ind_list[i][0]1);// }// return ret;// 1 dp// int n s.size();// vectorint dp(n, 0);// int ret 0;// for(int i 1; i n; i){// if(s[i] ) s[i-1] (){// if(i 2)// dp[i] dp[i-2] 2;// else// dp[i] 2;// }// else if(s[i] ) s[i-1] )){// if(i-1-dp[i-1] 0 s[i-1-dp[i-1]] (){// if(i-2-dp[i-1] 0)// dp[i] dp[i-1] 2 dp[i-2-dp[i-1]];// else // dp[i] dp[i-1] 2;// }// }// ret max(ret, dp[i]);// }// return ret;// 2 stackint n s.size();stackint stk;stk.push(-1);int ret 0;for(int i 0; i n; i){if(s[i] (){stk.push(i);}else{stk.pop();if(stk.empty()){stk.push(i);}else{ret max(ret, i-stk.top());}}}return ret;// 3// int n s.size();// int left 0, right 0;// int ret 0;// for(int i 0; i n; i){// if(s[i] (){// left;// }// else{// right;// }// if(left right){// ret max(ret, 2*left);// }// else if(right left){// right 0;// left 0;// }// }// left 0; right 0;// for(int i n-1; i 0; i--){// if(s[i] (){// left;// }// else{// right;// }// if(left right){// ret max(ret, 2*left);// }// else if(right left){// right 0;// left 0;// }// }// return ret;}
};
