嘉兴网站定制,制作网站站用的软件,网站建设 局部放大镜功能,建设和同城类似的网站Leetcode热题100-32 最长有效括号 1. 题目描述2. 解题思路动态规划栈解法 3. 代码实现动态规划栈解法 1. 题目描述
32 最长有效括号
2. 解题思路
动态规划
定义状态#xff1a;
设 dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。
状态转移方程#xff1a; 遍历字符… Leetcode热题100-32 最长有效括号 1. 题目描述2. 解题思路动态规划栈解法 3. 代码实现动态规划栈解法 1. 题目描述
32 最长有效括号
2. 解题思路
动态规划
定义状态
设 dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。
状态转移方程 遍历字符串 s当遇到 s[i] ) 时存在以下两种情况
情况 1s[i - 1] ( 当前字符 ) 与前一个字符 ( 组成了一对匹配的括号。更新状态 d p [ i ] ( i ≥ 2 ? d p [ i − 2 ] : 0 ) 2 dp[i] (i \geq 2 ? dp[i - 2] : 0) 2 dp[i](i≥2?dp[i−2]:0)2 情况 2s[i - 1] ) 需要满足条件i - dp[i - 1] 0即前面存在可以与当前 ) 匹配的 (。 d p [ i ] ( i − d p [ i − 1 ] ≥ 2 ? d p [ i − d p [ i − 1 ] − 2 ] : 0 ) d p [ i − 1 ] 2 dp[i] (i - dp[i - 1] \geq 2 ? dp[i - dp[i - 1] - 2] : 0) dp[i - 1] 2 dp[i](i−dp[i−1]≥2?dp[i−dp[i−1]−2]:0)dp[i−1]2其中 dp[i - dp[i - 1] - 2] 表示与当前匹配的 ( 前面的有效子串长度若存在否则为 0。dp[i - 1] 是前一个位置的最长有效子串长度。s[i - dp[i - 1] - 1] 与 s[i] 匹配长度为 2。
更新最大值 在遍历过程中更新最大长度 maxLen max ( maxLen , d p [ i ] ) \text{{maxLen}} \max(\text{{maxLen}}, dp[i]) maxLenmax(maxLen,dp[i]) 遍历结束后maxLen 即为所求结果。
栈解法
初始化
使用一个栈 stk 存储索引。将 -1 压入栈表示最后一个未匹配的右括号的索引。
遍历字符串
遍历字符串中的每个字符 如果当前字符为 (将其索引压入栈。如果当前字符为 ) 弹出栈顶元素表示尝试匹配最近的 (。如果栈为空说明没有匹配的 (将当前索引压入栈。如果栈不为空计算当前有效括号的长度并更新最大长度 maxLen maxLen max ( maxLen , i − stack.top() ) \text{{maxLen}} \max(\text{{maxLen}}, i - \text{{stack.top()}}) maxLenmax(maxLen,i−stack.top())
3. 代码实现
动态规划
class Solution {
public:// 使用栈来解决问题int longestValidParentheses(string s) {int maxLen 0;int n s.size();vectorint dp(n, 0);// 注意到子串是指字符串中连续的字符序列for (int i 1; i n; i) {if (s[i] )) {// 直接匹配if (s[i - 1] () {dp[i] (i 2 ? dp[i - 2] : 0) 2;}// s[i-1])else if (i - dp[i - 1] 0 s[i - dp[i - 1] - 1] () {// dp[i-dp[i-1]-2]表示与dp[i-1]相连的有效子字符串的长度// dp[i]由三部分组成// s[i-dp[i-1]-1]与s[i]匹配(长度为2)// dp[i - 1]// dp[i - dp[i - 1] - 2]或者为0dp[i] (i - dp[i - 1] 2 ? dp[i - dp[i - 1] - 2] : 0) dp[i - 1] 2;}}maxLen max(maxLen, dp[i]);}return maxLen;}
};栈解法
class Solution {
public:int longestValidParentheses(string s) {int res0;stackint stk;stk.push(-1);for(int i0;is.size();i){if(s[i](){stk.push(i);}else{stk.pop();if(stk.empty()){stk.push(i);}else{resmax(res,i-stk.top());}}}return res;}
};
