longestvalidparentheses方法歸納

2019-11-14 15:03:32

字體：大中小

供稿：網(wǎng)友

題目大意見leetcode，下面我稍微介紹下想到的三種方法：

方法一：不用棧去找匹配

建立一個數(shù)組l2表示匹配，然后i從0開始，看到 ( 就把l2對應(yīng)的數(shù)值記為-1，直到看到），找到）以后，從當(dāng)前i開始返回去找是否有匹配，此時(shí)如讀到），就看當(dāng)前的l2的對應(yīng)位置值是否為-1，如果不是就跳轉(zhuǎn)到所對應(yīng)的值的位置，繼續(xù)往前找，直到找到第一個（，將l2對應(yīng)值置為此時(shí)（的下標(biāo)，進(jìn)行下一次操作。如果是-1，就把當(dāng)前l(fā)2對應(yīng)位置的值也置為-1，表示沒有多余的匹配。遍歷一遍后，得到完整的數(shù)組l2，此時(shí)需要從l2得到最大的合法匹配。舉個例子：

對于字符串：）（（））（）（

首先讀到右括號，但是此時(shí)i=0，左邊不可能有匹配，所以l2[0]=-1

接著讀到左括號，l2[1]=-1,l2[2]=-1

此時(shí)讀到右括號，從當(dāng)前位置往前找，第一個就是左括號，所以l2[3]=2(此時(shí)左括號的下標(biāo))

接著又讀到右括號，從當(dāng)前位置往前找，先看到了右括號，此右括號的位置對應(yīng)的l2值不為-1，則調(diào)到對應(yīng)值-1的位置，此例子中跳到下標(biāo)為1的位置，讀到一個左括號，所以l2[4]=1

以此類推，此例中l(wèi)2={-1,-1,-1,2,1,-1,5,-1}

下面涉及到回復(fù)，我們可以看到l2中下標(biāo)與值的對應(yīng)就是原字符串中匹配的兩個左右括號的對應(yīng)，所以，此時(shí)，我們把這個對應(yīng)拿出來：3-2，4-1, 6-5。把這些值進(jìn)行排序，得到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，導(dǎo)致速度變慢了，如全用數(shù)組實(shí)現(xiàn)，會快一些。這個題目我用過好多辦法，發(fā)現(xiàn)幾乎使用List都沒過，只要一把List的方式換成數(shù)組，就能過。。。呵呵，給偷懶者當(dāng)頭一棒。

方法二：用棧去找匹配

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

    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;        }

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

方法三：動態(tài)規(guī)劃

動態(tài)規(guī)劃的核心在于找到最優(yōu)子問題的結(jié)構(gòu)和看是否有重復(fù)計(jì)算的子問題。此題中，如果一個字串是最長的合法串，那么它一定能由另一個子串構(gòu)造。從字符串s有后往前，我們考慮s上的每一個位置，要是這個位置的字符包含在最長子串中，則我們可以由這個子串的從第1個元素開始的子串的最大合法子串構(gòu)造。換言之，dp[i]表示從s[i]到s[s.length - 1] 包含s[i] 的最長的有效匹配括號子串長度，在s中從后往前，若s[i] == '('，則在s中從i開始到s.length - 1計(jì)算dp[i]的值。在s中尋找從i + 1開始的有效括號匹配子串長度，即dp[i + 1]，跳過這段有效的括號子串，查看下一個字符，其下標(biāo)為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;    }