火的网站建设明细报价表,网站建设中的服务器搭建方式,极速网站建设定制多少钱,新浪云主机上安装wordpress主题文章目录1. 题目信息2. 栈 解题3. 动态规划 解题1. 题目信息
给定一个只包含 ‘(’ 和 ‘)’ 的字符串#xff0c;找出最长的包含有效括号的子串的长度。
示例 1:输入: (()
输出: 2
解释: 最长有效括号子串为 ()
示例 2:输入: )()())
输…
文章目录1. 题目信息2. 栈 解题3. 动态规划 解题1. 题目信息
给定一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长的包含有效括号的子串的长度。
示例 1:输入: (()
输出: 2
解释: 最长有效括号子串为 ()
示例 2:输入: )()())
输出: 4
解释: 最长有效括号子串为 ()()来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 栈 解题
括号匹配一般都可以用栈解决这题是把相关的元素的下标出入栈
先把 -1push入栈遇见 push其下标入栈遇见 先弹栈后如果栈不为空则匹配了匹配长度count为当前 i-top记录最大的count即为答案如果栈为空就把未匹配的 下标压栈 class Solution
{
public:int longestValidParentheses(string s){int count 0, maxlen 0;stackint stk;stk.push(-1);for(int i 0; i s.size(); i){if(s[i] (){stk.push(i);}else // s[i] ){stk.pop();if(!stk.empty()){count i-stk.top();if(count maxlen)maxlen count;}elsestk.push(i);}}return maxlen;}
};3. 动态规划 解题
dp[i]表示包含第下标 i 个字符的情况下该子串匹配的最大长度
当s[i] ( 时这个子串肯定没有匹配记dp[i] 0所以dp数组初始化为0所以我们只要更新s[i] ) 时的dp[i]的值
分两种情况
s[i] ) s[i-1] (那说明 dp[i] dp[i-2] 2s[i] ) s[i-1] )在字符 i-1处匹配了dp[i-1] 个字符那么再往前一个字符的下标 k 是 i-1-dp[i-1]
检查s[k]如果其为 ‘(’ 那么下标 i 元素跟 s[k] 匹配了再检查下 k - 1处的匹配长度 dp[k]需要把他也加起来则 dp[i] dp[i-1] dp[k-1] 2如果 k-1 0则忽略 dp[k-1] 项如果 s[k] 为 ‘)’那么下标 i 元素与 s[k] 未匹配则包含 s[i]的子串是不匹配的所以 dp[i] 0已初始化0不必更新dp数组 class Solution
{
public:int longestValidParentheses(string s)// DP解法{if(s.size() 1)return 0;int dp[s.size()];int maxlen 0, k, i;memset(dp,0,s.size()*sizeof(int));for(i 1; i s.size(); i){if(s[i] )){if(s[i-1] (){if(i 2)dp[i] dp[i-2] 2;elsedp[i] 2;}else// s[i-1] ){k i-1-dp[i-1];if(k 0 s[k] (){if(k 1)dp[i] dp[i-1] dp[k-1] 2;elsedp[i] dp[i-1] 2;}}}}for(i 0; i s.size(); i){if(dp[i] maxlen)maxlen dp[i];}return maxlen;}
};
