longestvalidparentheses方法歸納

2019-11-14 15:03:32

字體：大中小

來源：轉載

供稿：網友

題目大意見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;       }

程序能通過，但是跑的并不快，原因在于最后用了List，導致速度變慢了，如全用數組實現，會快一些。這個題目我用過好多辦法，發現幾乎使用List都沒過，只要一把List的方式換成數組，就能過。。。呵呵，給偷懶者當頭一棒。

方法二：用棧去找匹配

這種方法就簡單很多了，兩個棧，一個用來壓入左右括號，另一個壓下標?？吹阶罄ㄌ柧蛪哼M去，看到右括號就進行判斷，比較簡單，直接貼代碼參考吧：

    public int longestValidParentheses(String s) {            int len=s.length();        int max=0;                Stack<Character> t1 = new Stack<Character>();                Stack<Integer> t2 = new Stack<Integer>();                      for(int i=0;i<len;i++){                        if(s.charAt(i)=='('){                                t1.push('(');                                t2.push(i);                        }            else{                                if(t1.size()>0 && t1.peek().equals('(')){                      t1.pop();                                       t2.pop();                                        int tmp=t2.size()==0?i+1:i-t2.peek();                                        max=Math.max(max,tmp);                                }                else{                                        t1.push(')');                                        t2.push(i);                                }                        }                }                return max;        }

用了棧，跑的也不快。。。

方法三：動態規劃

動態規劃的核心在于找到最優子問題的結構和看是否有重復計算的子問題。此題中，如果一個字串是最長的合法串，那么它一定能由另一個子串構造。從字符串s有后往前，我們考慮s上的每一個位置，要是這個位置的字符包含在最長子串中，則我們可以由這個子串的從第1個元素開始的子串的最大合法子串構造。換言之，dp[i]表示從s[i]到s[s.length - 1] 包含s[i] 的最長的有效匹配括號子串長度，在s中從后往前，若s[i] == '('，則在s中從i開始到s.length - 1計算dp[i]的值。在s中尋找從i + 1開始的有效括號匹配子串長度，即dp[i + 1]，跳過這段有效的括號子串，查看下一個字符，其下標為j = i + 1 + dp[i + 1]。若j沒有越界，并且s[j] == ‘)’，則s[i ... j]為有效括號匹配，dp[i] =dp[i + 1] + 2。在求得了s[i ... j]的有效匹配長度之后，若j + 1沒有越界，則dp[i]的值還要加上從j + 1開始的最長有效匹配，即dp[j + 1]。

    int longestValidParentheses(String s) {            int len = s.length();        if(len<2)          return 0;        int max = 0;        int []dp = new int[len];for(int i = len-2;i>=0;i--)        {          if(s.charAt(i) == '(')          {            int j = i+1+dp[i+1];            if(j<len && s.charAt(j) == ')')            {              dp[i] = dp[i+1] + 2;              if(j+1<len)                dp[i] += dp[j+1];            }            if(dp[i]>max)              max = dp[i];          }                  }        return max;    }