資訊專欄INFORMATION COLUMN
摘要：在問(wèn)題中，我們可以用來(lái)檢驗(yàn)括號(hào)對(duì)，也可以通過(guò)來(lái)檢驗(yàn)。遇到就加一，遇到就減一。找到一對(duì)括號(hào)就在最終結(jié)果上加。我們用來(lái)表示當(dāng)前位置的最長(zhǎng)括號(hào)。括號(hào)之間的關(guān)系有兩種，包含和相離。
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問(wèn)題中，我們可以用stack來(lái)檢驗(yàn)括號(hào)對(duì)，也可以通過(guò)count來(lái)檢驗(yàn)。遇到"("就加一，遇到")"就減一。找到一對(duì)括號(hào)就在最終結(jié)果上加2。
我們用value[i]來(lái)表示當(dāng)前位置的最長(zhǎng)括號(hào)。
括號(hào)之間的關(guān)系有兩種，包含：() 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) {
//包含關(guān)系，通過(guò)最近的括號(hào)長(zhǎng)度來(lái)改變。
// () dp[1] = dp[0] +2
// (()) dp[2] = dp[1] +2 =2, dp[3] = dp[2] +2 = 4
value[i] = 2 + value[i-1];
//相離關(guān)系，通過(guò)相離的括號(hào)長(zhǎng)度來(lái)改變。
// ()() 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66293.html
摘要：假設(shè)是從下標(biāo)開(kāi)始到字符串結(jié)尾最長(zhǎng)括號(hào)對(duì)長(zhǎng)度，是字符串下標(biāo)為的括號(hào)。如果所有符號(hào)都是，說(shuō)明是有效的。 Longest Valid Parentheses Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) 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...
摘要：題目要求原題地址一個(gè)括號(hào)序列，求出其中成對(duì)括號(hào)的最大長(zhǎng)度思路一使用堆棧這題可以參考我的另一篇博客這篇博客講解了如何用堆棧判斷括號(hào)序列是否可以成對(duì)。我們可以將堆棧的思路延續(xù)到這里。在這里需要先遍歷一遍字符串，再遍歷一下非空的堆棧。 題目要求 原題地址：https://leetcode.com/problems... Given a string containing just the c...
摘要：前言從開(kāi)始寫(xiě)相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開(kāi)始寫(xiě)leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要：自己沒(méi)事刷的一些的題目，若有更好的解法，希望能夠一起探討項(xiàng)目地址 自己沒(méi)事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
閱讀 2333·2023-04-26 00:28
閱讀 3080·2019-08-30 15:55
閱讀 2752·2019-08-30 12:47
閱讀 1562·2019-08-29 11:04
閱讀 3190·2019-08-28 18:14
閱讀 954·2019-08-28 18:11
閱讀 1682·2019-08-26 18:36
閱讀 3397·2019-08-23 18:21
