国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[leetcode]Longest Valid Parentheses

qujian / 2011人閱讀

摘要:在問題中,我們可以用來檢驗括號對,也可以通過來檢驗。遇到就加一,遇到就減一。找到一對括號就在最終結果上加。我們用來表示當前位置的最長括號。括號之間的關系有兩種,包含和相離。

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.

在valid parentheses問題中,我們可以用stack來檢驗括號對,也可以通過count來檢驗。遇到"("就加一,遇到")"就減一。找到一對括號就在最終結果上加2。
我們用value[i]來表示當前位置的最長括號。
括號之間的關系有兩種,包含:() or (()) or ((()))和相離()() or ()(())。

public class Solution {
    public int longestValidParentheses(String s) {
        char[] chs = s.toCharArray();
        int[] value = new int[chs.length];
        int open = 0;
        int max = 0;
        
        for(int i=0; i < chs.length; i++){
            if(chs[i] == "(") open++;
            if(chs[i] == ")" && open > 0) {
                //包含關系,通過最近的括號長度來改變。
                // ()    dp[1] = dp[0] +2
                // (())  dp[2] = dp[1] +2 =2,  dp[3] = dp[2] +2 = 4
                value[i] = 2 + value[i-1];
                //相離關系,通過相離的括號長度來改變。
                // ()()  dp[3] = dp[3] + dp[1] = 2 + 2 = 4
                if(i-value[i] > 0){
                    value[i] += value[i-value[i]];
                }
                open--;
            }
            if(value[i] > max) max = value[i];
        }
        
        return max;
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66293.html

相關文章

  • [Leetcode] Longest Valid Parentheses 最長有效括號對

    摘要:假設是從下標開始到字符串結尾最長括號對長度,是字符串下標為的括號。如果所有符號都是,說明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses...

    everfight 評論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 評論0 收藏0
  • leetcode32 Longest Valid Parentheses 最長括號組的長度

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

    happyhuangjinjin 評論0 收藏0
  • leetcode 部分解答索引(持續更新~)

    摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0
  • leetcode部分題目答案之JavaScript版

    摘要:自己沒事刷的一些的題目,若有更好的解法,希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目,若有更好的解法,希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

    alphahans 評論0 收藏0

發表評論

0條評論

qujian

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<