三语网站建设,p站关键词排名,网络营销的特点和职能,怎么样推广自己的网址题目介绍
给你一个只包含 ( 和 ) 的字符串#xff0c;找出最长有效#xff08;格式正确且连续#xff09;括号子串的长度。
示例 1#xff1a; 输入#xff1a;s (() 输出#xff1a;2 解释#xff1a;最长有效括号子串是 () 示例 2#xf…题目介绍
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
示例 1 输入s (() 输出2 解释最长有效括号子串是 () 示例 2 输入s )()()) 输出4 解释最长有效括号子串是 ()() 使用栈解决
这题让求的是最长有效括号长度一个有效的括号一定是满足下面两个条件 左括号和右括号的数量一定是相等的。 在有效括号的任何位置左括号的数量一定是大于等于右括号的数量。
根据这两个特性我们可以使用栈来解决栈中存放的是字符的下标解决思路就是 如果遇到左括号我们就把他的下标压栈。 如果遇到右括号栈顶元素出栈如果栈不为空说明出栈的元素和这个右括号匹配我们需要计算他们的长度保留最大值即可。如果栈为空直接把这个右括号所在的下标压栈。
这里要注意如果给定的字符串从一开始就是有效的括号比如()())前4个符号是有效的括号我们是没法计算他的长度的因为第一个字符前面是没有字符的所以我们默认第一个字符前面的下标是-1然后把他压栈我们以示例2为例画个图来看下。 最后看下代码
class Solution {
public:int flags[20000];int longestValidParentheses(string s) {int n s.size();stackint stk;//存储的是下标for(int i 0; i n; i){if(s[i] () stk.push(i);//左括号pushelse{if(stk.empty()) flags[i] 1;else stk.pop();}}while(!stk.empty()){flags[stk.top()] 1;stk.pop();}int res 0, len 0;for(int i 0; i n; i){if(flags[i] 0) len;else{res max(res, len);//长度更新len 0;}}return max(res, len);//可能需要考虑最后的位}
};动态规划
再来看下动态规划该怎么解决我们用dp[i]表示以是s[i]为结尾的最长有效括号长度如果要计算dp[i]就会有下面几种情况 第i个字符是左括号(那么以他结尾的是构不成有效括号的所以dp[i]0; 第i个字符是右括号)那么以他结尾的是有可能构成有效括号的所以还需要继续判断 这里我们需要判断他前面的也就是第i-1个字符如果第i-1个字符是左括号(类似于……()那么最长有效括号就是第i-2个字符之前构成的最长有效括号2也就是dp[i]dp[i-2]2。 如果第i-1个字符也是右括号)类似于……((……))如下图所示我们还需要判断第i -1- dp[i - 1]个字符是否是左括号(,如果是(那么递推公式是dp[i] dp[i - 1] 2 dp[i - dp[i - 1] - 2]这里dp[i - dp[i - 1] - 2]是第一个省略号构成的有效括号长度这个不要忘了。 最后看下代码
class Solution {
public:int dp[20000];int longestValidParentheses(string s) {int n s.size();for(int i 1; i n; i){if(s[i] )){//合法的子串一定以右括号结尾if(s[i-1] () dp[i1] dp[i-1] 2; else if(i-1-dp[i] 0 s[i-1-dp[i]] () dp[i1] dp[i] dp[i-1-dp[i]] 2;} }return *max_element(dp1, dpn1);}
};
