当前位置:网站首页>【力扣刷题】32. 最长有效括号

【力扣刷题】32. 最长有效括号

2022-07-06 12:56:00 李小恩恩子

目录

题目:

方法一

解题思路:

代码:

方法二:

解题思路:

代码:

题目:

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

方法一:

解题思路:

利用栈,学过利用栈来判断一个只包含'('和')'的字符串是否是括号匹配的,那个题目解题就是,遍历整个字符串,是左括号就入栈,是右括号则①判断栈是否有左括号且弹出一个左括号,②如果栈为空则为false,如果所有字符都遍历完了,栈中还有元素则为false,否则为true。

利用这个思路,增加一个标记数组arr,初始化所有元素为1,栈中存的是数组下标(字符索引)。遍历整个字符串,如果是左括号则把索引下标(i)加入栈,如果是右括号则判断栈中元素是否为空且不为空则弹出,并把标记数组对应的元素arr[stack.pop()]以及当前下标对应的标记数组元素arr[i]置为0。

最后判断标记数组arr的最长连续0就可以了。

代码:

class Solution {
    public int longestValidParentheses(String s) {
        //要找最长的有效括号
        //栈
        //利用栈来标记左右括号是否有效,栈的内容存下标i
        Stack<Integer> stack = new Stack<>();
        int[] valid = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            valid[i] = 1;
        }
        for(int i = 0; i < s.length();i++){
            if(s.charAt(i) == '(') stack.push(i);
            else{
                if(!stack.empty()){
                    valid[i] = 0;
                    valid[stack.pop()] = 0;
                }
            }
        }
        int res = 0,count = 0;
        for(int i = 0; i < s.length();i++){
            if(valid[i] == 1) {
                count = 0;
            }else{
                count++;
            }
            res = Math.max(res,count);
        }
        return res;
    }
}

方法二:

解题思路:

动态规划,利用dp[i]表示以下标i字符结尾的最长有效括号的长度。将dp数组全部初始化为0。有效的子串一定以')'结尾,以'('结尾的子串对应的dp值必定为0。所以只需要求解以')'在dp数组中对应位置的值。所以从前往后遍历字符串,求解dp值。

①s.charAt(i)=')'且s.charAt(i-1)='(',字符串为"...()"则dp[i] = dp[i-2]+2。

②如果s.charAt(i) = ')'且s.charAt(i-1) = ')',比如字符串"...))"->"()(())",

如果s.charAt(i - dp[i - 1] - 1)='(',那么有效括号长度新增长度2,i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2,不过得注意,i − dp[i − 1] − 1 和 i 组成了有效括号对,这将是一段独立的有效括号序列,如果之前的子序列是形如 (...)(...) 这种序列,那么当前位置的最长有效括号长度还需要加上这一段。例如:()(()),左边红色的右边绿色的为两个独立的有效括号序列。所以状态转移方程为:dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] -2 ]。

图示: 

还要注意边界值,因为要用到 dp[ i - 2 ],还有dp[ i - dp[ i - 1 ] - 2 ],要判断。  

代码:

class Solution {
    public int longestValidParentheses(String s) {
        //动态规划
        //dp[i]表示以下标i字符结尾的最长有效括号的长度
        int res = 0;
        int[] dp = new int[s.length()];
        for(int i = 1;i < s.length();i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    if(i >= 2) dp[i] = dp[i - 2] + 2;
                    else dp[i] = 2;
                }else if(i - dp[i - 1] > 0  && s.charAt(i - dp[i - 1] - 1) == '('){
                    if(i - dp[i - 1] >= 2) dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    else dp[i] = dp[i - 1] + 2;
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

方法二看了看解析,不太会写动态规划,下次找个机会专门练一练动态规划的题目。 

原网站

版权声明
本文为[李小恩恩子]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_45704996/article/details/125569685