longest valid parentheses方法归纳

    题目大意见leetcode，下面我稍微介绍下想到的三种方法：

    方法一：不用栈去找匹配

    建立一个数组l2表示匹配，然后i从0开始，看到 ( 就把l2对应的数值记为-1，直到看到 ），找到）以后，从当前i开始返回去找是否有匹配，此时如读到），就看当前的l2的对应位置值是否为-1，如果不是就跳转到所对应的值的位置，继续往前找，直到找到第一个（，将l2对应值置为此时（的下标，进行下一次操作。如果是-1，就把当前l2对应位置的值也置为-1，表示没有多余的匹配。遍历一遍后，得到完整的数组l2，此时需要从l2得到最大的合法匹配。举个例子：

     对于字符串：）（（））（）（

     首先读到右括号，但是此时i=0，左边不可能有匹配，所以l2[0]=-1

     接着读到左括号，l2[1]=-1,l2[2]=-1

     此时读到右括号，从当前位置往前找，第一个就是左括号，所以l2[3]=2(此时左括号的下标)

     接着又读到右括号，从当前位置往前找，先看到了右括号，此右括号的位置对应的l2值不为-1，则调到对应值-1的位置，此例子中跳到下标为1的位置，读到一个左括号，所以l2[4]=1

     以此类推，此例中l2={-1,-1,-1,2,1,-1,5,-1}

    下面涉及到回复，我们可以看到l2中下标与值的对应就是原字符串中匹配的两个左右括号的对应，所以，此时，我们把这个对应拿出来：3-2，4-1, 6-5。把这些值进行排序，得到1,2,3,4,5,6，可以看出要求的值，即为此排序中最大那个序列的长度（此序列以1为等差递增）。如1,2,3,4,5,6,9,10,11,12中有两个序列1,2,3,4,5,6和9,10,11,12.而最长的那个序列的长度即为我们所求。

    代码如下：

public int longestValidParentheses(String s) {      int max=0;    int[] l2=new int[s.length()];    char[] ch=s.toCharArray();    for(int i=0;i<ch.length;i++){      if(ch[i]=='('){l2[i]=-1;}      else{        for(int j=i-1;j>=0;){          if(ch[j]==')'&&l2[j]!=-1){            j=l2[j]-1;            if(j<0){l2[i]=-1;break;}          }          else if(ch[j]==')'&&l2[j]==-1){l2[i]=-1;break;}          else if(ch[j]=='('){l2[i]=j;break;}        }        if(i==0&&ch[0]==')'){l2[i]=-1;}       }     }     List<Integer>l3=new ArrayList<Integer>();     for(int i=0;i<s.length();i++){       if(l2[i]!=-1){l3.add(l2[i]);l3.add(i);}     }     Collections.sort(l3);     int inter=0;     for(int i=0;i<l3.size()-1;i++){       if(l3.get(i+1)==l3.get(i)+1){inter++;max=Math.max(inter, max);}       else {max=Math.max(inter, max);inter=0;}     }     return max>0?max+1:0;    }

        
 
        
海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com
        

        
原标题：longest valid parentheses方法归纳
        
关键词：