文章目錄

• 題目描述
• 代碼 & 解析
• • • 1. 棧做法
    • 2. 動態規劃

題目描述

• （括號題真的好煩人）
• 講道理，題目一看，大概率就是用dp做
  

代碼 & 解析

1. 棧做法

• 這個做法我沒實際寫，但是感覺很厲害，就記錄一下。
• 我們之前做括號正確判斷的時候，就用到了棧來進行匹配判斷。
  如今也可以用棧來進行正確判斷，并記錄下可行的括號的下標，
  比如（1，4）（2，3）（7，8），得到142378，而后一次排序O(nlogn)，得到123478。
  在這個有序數組中找到最長連續子串即可。
  （當然，這里可以優化成O(n)，排序用其他方法代替。）

2. 動態規劃

• 具體見注釋

/*** 使用dp做法* 我是覺得，難點在于考慮dp數組的設計（一維、二維）* 以及dp數組存儲值代表的意思* 再就是循環的設計（頭到尾、尾到頭、短到長）* 最后是狀態轉移方程的設計，這個要根據實際問題來，感覺是最難的：* 1. 有哪幾種轉移情況？(分類，真的不容易：要找出最合適的分類，并且要分類包括所有情況)* 2. 為什么轉移，為什么可以這么轉移 */class Solution {public int longestValidParentheses(String s) {if (s == null || s.length() == 0){return 0;}int ans = 0;int len = s.length();// dp[i]代表以s.charAt[i]結尾的最長有效括號int[] dp = new int[len];// O(n)for (int i=0; i<len; i++){char ch = s.charAt(i);// 這種情況肯定是0，"xxxxxxx...("，以這玩意結尾必然無效：可以省略不寫，默認為0/*if(ch == '('){dp[i] = 0;}*/// ')'有兩種情況if(i > 0 && ch == ')'){// 剛好契合的情況，構成"xxxxxx()"if(s.charAt(i-1) == '(') {// 加上之前的最長有效括號dp[i] = i-2 >= 0? dp[i-2] + 2 : 2;}// "xxxxxx))"的情況else{// 用【】來代表dp[i]組成的括號："xx【xxxxx)】"// 此時 s.charAt[i - dp[i-1]-1]可能是數組越界，或者是'('、')'int left = i - dp[i-1]-1;if(left >= 0 && s.charAt(left)=='('){dp[i] = left-1>=0?dp[i-1]+2+dp[left-1] : dp[i-1] + 2;// "x【"中延續x的長度}/* //可以省略，默認0else{dp[i] = 0;}*/}ans = Math.max(dp[i],ans);}}return ans;} }

• 整理一下

class Solution {public int longestValidParentheses(String s) {if (s == null || s.length() == 0){return 0;}int ans = 0;int len = s.length();// dp[i]：以s.charAt[i]結尾的最長有效括號int[] dp = new int[len];// O(n)for (int i=0; i<len; i++){char ch = s.charAt(i);// Case 1: "xx("，以'('結尾必然無效，默認為0// Case 2: ')'有兩種情況if(i > 0 && ch == ')'){// 剛好契合的情況，構成"xxxxxx()"if(s.charAt(i - 1) == '(') {// 加上之前的最長有效括號dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;}// "xxxxxx))"的情況else{// 用【】來代表dp[i]組成的括號："xx【xxxxx)】"// 此時 s.charAt[i - dp[i-1]-1]可能是數組越界，或者是'('、')'int left = i - dp[i - 1] - 1;if(left >= 0 && s.charAt(left)=='('){dp[i] = left - 1 >= 0 ? dp[i - 1] + 2 + dp[left - 1] : dp[i - 1] + 2;// "x【"中延續x的長度}// else 為默認0，省略不寫}ans = Math.max(dp[i], ans);}}return ans;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】32. 最长有效括号（Java、动态规划、栈、字符串）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。