最长的括号子串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        // 固定套路的分类讨论dp
        // 定义子问题：以i结尾的最长括号字串
        // 情况1：以(结尾，就是0
        // 情况2：以)结尾，那就到子问题的最长括号的起始位置的前一个位置，看能否有"("
        int len = s.length();
        int res = 0;
        int[] dp = new int[len + 1];
        for(int i = 1; i <= len; i++) {
           if(s.charAt(i - 1) == ')' && (i - dp[i - 1] - 2 >= 0) && s.charAt(i - dp[i - 1] - 2) == '(') {
                dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
            }   
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    // 参考：https://b23.tv/1MZoUWh
    public int longestValidParentheses (String s) {
        // write code here
        // dp[i]表示以s.charAt(i)结尾的最长子括号子串
        int[] dp = new int[s.length()];
        int max = 0;
        // 以左括号结尾的dp肯定为0,因此递推公式只需要考虑右括号结尾即可
        for (int i = 1; i < s.length(); i++) {
            // s.charAt(i) == ')'表示s的i位置字符为右括号，右括号才能与i之前的左括号闭合成正确的子串
            // i - dp[i - 1] - 1为是与当前右括号闭合的左括号的下标，当前右括号的下标为i，i-1的最长括号
            // 子串长度为dp[i-1],则当前右括号闭合的左括号的下标为i - dp[i - 1] - 1。dp[i-1]的值只考虑
            // 当前右括号和当前右括号闭合的左括号所夹区域的括号。(i - dp[i - 1] - 1) < 0表示当前右括号
            // 无闭合的左括号，即向左去寻找闭合的左括号，寻至首个也首字符也未找到，直至越界，则此时
            // 应有dp[i]=0,dp已经初始化为0
            // s.charAt(i - dp[i - 1] - 1) == '('表示找到当前右括号闭合的左括号，只有找到闭合的左括号
            // dp[i]才能不计为0
            if (s.charAt(i) == ')' && (i - dp[i - 1] - 1) >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                // 2表示当前右括号与左括号的长度。dp[i - 1] 表示以当前右括号的前一个括号结尾的s的长度，即
                // 当前右括号和与它闭合的左括号所夹的最长子串长度。dp[i - dp[i - 1] - 2]表示当前右括号的闭合
                // 左括号的前一个括号的对应的最长子串长度，越界时计为0
                dp[i] =2 + dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
            } 
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

 public int longestValidParentheses (String s) {
        //长度：当前索引-栈顶索引
        Stack<Integer> st=new Stack<>();
        st.push(-1);//避免第一个是），造成异常，初始化栈顶为-
        int ans=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){//栈记录左括号下标，左括号入栈
                st.push(i);
            }else{
                st.pop();//遇到右括号，弹出左括号下标
                if(st.isEmpty()){//栈为空，记录上一次结束的位置
                    st.push(i);
                }else{//栈不空，说明栈中还有左括号，右括号不够用，减去栈顶位置就是长度
                    ans=Math.max(ans,i-st.peek());//长度更新为：当前下标和栈顶下标的距离  （括号长度）
                }
            }
        }
        return ans;
    }

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        // 单序列问题，每一位存储以当前位置结尾的最长子串长度
        if(s.length()<=1)return 0;
        int len=s.length();
        int[] dp=new int[len];
        int l=0;
        int res=0;
        Stack<Integer> stack=new Stack();
        while(l<len){
            // 如果当前是左括号，入栈
            if(s.charAt(l)=='('){
                stack.push(l);
                l++;
            }
            else{
            // 如果是右括号，出栈
                if(stack.isEmpty()){
                    l++;
                }
                else{
                    int top=stack.pop();
                    dp[l]=l-top+1;
                    if(top>0){
                        dp[l]+=dp[top-1];
                    }
                    res=Math.max(res,dp[l]);
                    l++;
                }
            }
        }  
        return res;
    }
}

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        int len = s.length();
        if(len == 0){
            return 0;
        }

        // 定义dp， dp[i] = 当前0 ~ i个字符，有效括号的长度
        int[] dp = new int[len];
        char[] chars = s.toCharArray(); // 字符数组
        int result = 0; // 返回值
        int pre = -1;   // 指向
        // 遍历字符数组，从1开始，因为0位置无论是左括号 还是 右括号，能组成的有效括号长度都是0
        for (int i = 1; i < chars.length; i++) {
            // i只匹配右括号，遇到左括号它并不能组成括号，所以忽略
            if(chars[i] == ')'){ 
                // 当i是 ) 时，需要看 i - 1 位置的有效括号长度是多少，
                //  假设此时i = 3， i-1的位置 在dp中记录的有效长度是2， 
                //      那么需要向前看 i - 2 - 1位置，也就是i-1有效长度的再前一个位置的结果
                pre =  i - dp[i - 1] - 1;
                // 如果这个pre不越界，并且在char数组中等于( ，那么说明它能跟当前i字符) 匹配成一个有效括号
                if(pre >= 0 && chars[pre] == '('){
                    // 那么dp[i] 的有效括号长度，最起码是 dp[i-1] + 2
                    // 但还需要再累加上 pre-1的索引在dp记录的有效长度，如果越界则累加0，如果不越界，则累加dp[pre - 1]
                   dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }
            // 每次循环都将dp[i] 与 result 取最大值
            result = Math.max(result, dp[i]);
        }

        // 循环结束，result为解
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        Deque<Integer> stack = new ArrayDeque<>();
        int n = s.length();
        int[] flag = new int[n];

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') stack.push(i);
            else {
                if (stack.isEmpty()) flag[i] = 1;
                else stack.pop();
            }
        }

        while (!stack.isEmpty()) {
            flag[stack.pop()] = 1;
        }

        int res = 0, l = 0;
        for (int i = 0; i < n; i++) {
            if (flag[i] == 1) {
                l = 0;
                continue;
            }
            l++;
            res = Math.max(res, l);
        }

        return res;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        if(s.length()==0){return 0;}
        if(s.length()==1){return 0;}
        Deque<Integer> stack=new LinkedList<Integer>();
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<=s.length()-1;i++){
            char c=s.charAt(i);
            if(c=='('){stack.push(i);}
            if(c==')'){
                if(!stack.isEmpty()){
                    list.add(stack.pop());
                    list.add(i);
                }
            }
        }
        return max_length(list);
        
        
        
        
    }
    public int max_length(ArrayList<Integer> list){
        if(list.isEmpty()){return 0;}
        Collections.sort(list);
        int[] arr=new int[list.size()];
        for(int i=0;i<=list.size()-1;i++){
            arr[i]=list.get(i);
        }
        
        int[] dp=new int[arr.length];
        dp[0]=1;
        for(int i=1;i<=arr.length-1;i++){
            if(arr[i-1]==arr[i]-1){
                dp[i]=dp[i-1]+1;
            }else{
                dp[i]=1;
            }
        }
        int max=dp[0];
        for(int i=0;i<=dp.length-1;i++){
            max=dp[i]>max?dp[i]:max;
        }
        return max;
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        int len = s.length();
        if(len == 0) return 0;
        int max = 0;
        int l = 0 , r = 0;
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == '('){
                l++;
            }
            if(s.charAt(i) == ')'){
                r++;
            }
            if(l == r){
                max = max > 2 * r ? max : 2 * r;
            }
            if(l < r){
                l = 0;
                r = 0;
            }
        }
        l = 0;
        r = 0;
        for(int i = len - 1; i >= 0 ;i--){
            if(s.charAt(i) == '('){
                l++;
            }
            if(s.charAt(i) == ')'){
                r++;
            }
            if(l == r){
                max = max > 2 * r ? max : 2 * r;
            }
            if(l > r){
                l = 0;
                r = 0;
            }
        }
        return max;
    }
}

public int longestValidParentheses(String s) {
    if (s == null || s.length() < 2) {
        return 0;
    }
    int[] dp = new int[s.length()];
    if (s.charAt(0) == '(' && s.charAt(1) == ')') {
        dp[1] = 2;
    }
    int res = Math.max(dp[1], 0);
    for (int i = 2; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                dp[i] = 2 + dp[i - 2];
            } else {
                int index = i - dp[i - 1] - 1;
                if (index >= 0 && s.charAt(index) == '(') {
                    dp[i] = 2 + dp[i - 1];
                    if (index - 1 >= 0) {
                        dp[i] += dp[index - 1];
                    }
                }
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

        int max=0,n=s.length();
        int[]dp=new int[n];//dp[i]表示以i结尾的括号子串的长度
        for(int i=1;i<n;i++){
            if(s.charAt(i)==')'){//只对右括号的情况进行分析
                if(s.charAt(i-1)=='('){
                   dp[i]=(i<2?0:dp[i-2])+2;
                }
                else{ //如果j=i-dp[i-1]-1位置（也就是dp[i-1]括号字串的前一个元素）是'(',则增加了匹配长度
            //那么扩展之后的字串长度=dp[i-1]的长度+2+dp[j-1]位置匹配的长度
                    int j=i-dp[i-1]-1;
                    if(j>=0&&s.charAt(j)=='('){
                        dp[i]=dp[i-1]+(j-1>=0?dp[j-1]:0)+2;//2是i位置的）和j位置的(匹配的
                    }
                }
               
            }
             max=Math.max(max,dp[i]);
        }
        return max;

import java.util.*;


public class Solution {

    public int longestValidParentheses (String s) {
        Stack<Integer> stack = new Stack<>(); // 设定栈，存储左括号
        stack.push(-1); // 压入-1，处理边界问题
        int res = 0; // 结果存储变量
        
        for (int i = 0;i < s.length();i++) {
            // 如果是左括号则直接入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            }else {
                // 如果是右括号，则弹栈
                stack.pop();
                // 判空，若栈为空，则说明i左侧已经没有可用的左括号，此时将i压入栈中，防止空栈异常
                if (stack.isEmpty()) {
                    stack.push(i);
                }else {
                    // 长度计算时无需加1，因为预先弹栈，相当于已经加过1，且在01边界上因为初始化时压入-1进栈，因此也得以解决
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        
        return res;
    }
}