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

資訊專欄INFORMATION COLUMN

[LeetCode] 32. Longest Valid Parentheses

Flink_China / 1626人閱讀

Problem

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution DP
class Solution {
    public int longestValidParentheses(String s) {
        //()((()))
        //()()()()
        int max = 0, left = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == "(") left++;
            else {
                if (left != 0) {
                    dp[i] = dp[i-1]+2;
                    if (i-dp[i] >= 0) dp[i] += dp[i-dp[i]];
                    max = Math.max(max, dp[i]);
                    left--;
                }
            }
        }
        return max;
    }
}
Stack
class Solution {
    public int longestValidParentheses(String s) {
        //stack to store index
        Stack stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ")" && !stack.isEmpty() && s.charAt(stack.peek()) == "(") {
                //remove this pair
                stack.pop();
                
                //update the length of this pair
                //
                //if starts with )
                if (!stack.isEmpty()) max = Math.max(max, i-stack.peek());
                //if starts with (
                else max = i+1;
            } else {
                stack.push(i);
            }
        }
        return max;
    }
}

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

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

相關文章

  • leetcode32 Longest Valid Parentheses 最長括號組的長度

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

    happyhuangjinjin 評論0 收藏0
  • [leetcode]Longest Valid Parentheses

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

    qujian 評論0 收藏0
  • [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 部分解答索引(持續更新~)

    摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫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條評論

Flink_China

|高級講師

TA的文章

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