亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Longest Valid Parentheses 最長有效括號(hào)對(duì)

everfight / 2886人閱讀

摘要：假設(shè)是從下標(biāo)開始到字符串結(jié)尾最長括號(hào)對(duì)長度，是字符串下標(biāo)為的括號(hào)。如果所有符號(hào)都是，說明是有效的。

Longest Valid Parentheses 
Given a string containing just the characters "(" and ")", find the length of the longest valid (well-formed) parentheses substring.


For "(()", the longest valid parentheses substring is "()", which has length = 2.


Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
棧法 Stack 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

用Stack的方法本質(zhì)上和Valid Parentheses是一樣的，一個(gè)右括號(hào)能消去Stack頂上的一個(gè)左括號(hào)。不同的是，為了能夠計(jì)算括號(hào)對(duì)的長度我們還需要記錄括號(hào)們的下標(biāo)。這樣在彈出一個(gè)左括號(hào)后，我們可以根據(jù)當(dāng)前坐標(biāo)減去棧中上一個(gè)（也就是Pop過后的Top元素）的坐標(biāo)來得到該有效括號(hào)對(duì)的長度。

代碼 
public class Solution {
    public int longestValidParentheses(String s) {
        Stack stk = new Stack();
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++){
            //遇到左括號(hào)，將其push進(jìn)棧
            if(s.charAt(i)=="("){
                stk.push(new Parenthese(i, "("));
            } else {
           //遇到右括號(hào)，分類討論
               //如果當(dāng)前棧頂是左括號(hào)，則消去并計(jì)算長度
                if(!stk.isEmpty() && stk.peek().symb=="("){
                    int curLen = 0;
                    stk.pop();
                    if(stk.isEmpty()){
                        curLen = i + 1;
                    } else {
                        curLen = i - stk.peek().indx;
                    }
                    maxLen = Math.max(maxLen, curLen);
                } else {
               //如果棧頂是右括號(hào)或者是空棧，則將右括號(hào)也push進(jìn)棧，它的坐標(biāo)將方便之后計(jì)算長度
                    stk.push(new Parenthese(i, ")"));
                }
            }
        }
        return maxLen;
    }
    
    public class Parenthese {
        int indx;
        char symb;
        public Parenthese (int i, char s){
            this.indx = i;
            this.symb = s;
        }
    }
}
動(dòng)態(tài)規(guī)劃法 Dynamic Programming 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

動(dòng)態(tài)規(guī)劃法將大問題化為小問題，我們不一定要一下子計(jì)算出整個(gè)字符串中最長括號(hào)對(duì)，我們可以先從后向前，一點(diǎn)一點(diǎn)計(jì)算。假設(shè)d[i]是從下標(biāo)i開始到字符串結(jié)尾最長括號(hào)對(duì)長度，s[i]是字符串下標(biāo)為i的括號(hào)。如果s[i-1]是左括號(hào)，如果i + d[i] + 1是右括號(hào)的話，那d[i-1] = d[i] + 1。如果不是則為0。如果s[i-1]是右括號(hào)，因?yàn)椴豢赡苡杏依ㄌ?hào)開頭的括號(hào)對(duì)，所以d[i-1] = 0。

代碼 
public class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int maxLen = 0;
        for(int i = s.length()-2; i >=0; i--){
            if(s.charAt(i)=="("){
                int end = i + dp[i+1] + 1;
                if(end < s.length() && s.charAt(end)==")"){
                    dp[i] = dp[i+1] + 2;
                    if(end + 1 < s.length()){
                        dp[i] += dp[end + 1];
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}
后續(xù) Follow Up

Q：能否不用額外空間求解？
A：可以，但是要提高時(shí)間復(fù)雜度。比如((()())，先遍歷一遍將所有的()替換成00，得到((0000)，再遍歷一遍，替換所有的(00...00)這種形式字符串為000...000，這里我們得到(000000，直到遍歷完無法替換更多括號(hào)為之。如果所有符號(hào)都是0，說明是有效的。這樣的時(shí)間復(fù)雜度是O(N)。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/66168.html

相關(guān)文章

  • leetcode32 Longest Valid Parentheses 最長括號(hào)組的長度

    摘要：題目要求原題地址一個(gè)括號(hào)序列，求出其中成對(duì)括號(hào)的最大長度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號(hào)序列是否可以成對(duì)。我們可以將堆棧的思路延續(xù)到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。 題目要求 原題地址：https://leetcode.com/problems... Given a string containing just the c...

    happyhuangjinjin 評(píng)論0 收藏0

  • [leetcode]Longest Valid Parentheses

    摘要：在問題中，我們可以用來檢驗(yàn)括號(hào)對(duì)，也可以通過來檢驗(yàn)。遇到就加一，遇到就減一。找到一對(duì)括號(hào)就在最終結(jié)果上加。我們用來表示當(dāng)前位置的最長括號(hào)。括號(hào)之間的關(guān)系有兩種，包含和相離。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the lon...

    qujian 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • [LeetCode] 32. Longest Valid Parentheses

    Problem Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: (()Output: 2Explanation: The longest valid pa...

    Flink_China 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<