目录
- 1- 思路
- 题目识别
- 动态规划
- 2- 实现
- ⭐32. 最长有效括号——题解思路
- 3- ACM 实现
- 原题链接:32. 最长有效括号
1- 思路
题目识别
- 识别1 :给定一个字符串
s
,求解s
中的最长有效括号
动态规划
动态规划五部曲
- 递推公式难
- 如果遇到了
s.charAt(i) == ')'
开始递推 - 先求解
preIndex = i - dp[i-1] - 1
- 保证
preIndex >= 0 && s.charAt(preIndex) == '('
dp[i] = 2 + dp[i-1];
if(preIndex -1 >= 0) { dp[i] += dp[preIndex-1];}
- 保证
2- 实现
⭐32. 最长有效括号——题解思路
class Solution {public int longestValidParentheses(String s) {int len = s.length();if(len==0){return 0;}int res = 0;// 定义 dp数组// 有效括号长度int[] dp = new int[len];// 递推// preIndex = i - dp[i-1] -1;// if(preIndex >= 0 && s.charAt(preIndex == '('))// dp[i] = 2+dp[i-1];// if(preIndex - 1 >= 0 ) dp[i]+=dp[preIndex-1];// 3.初始化// 4.遍历for(int i = 1 ; i < len ; i++){if(s.charAt(i) == ')'){int pre = i - dp[i-1]-1;if(pre>=0 && s.charAt(pre)=='('){dp[i] = 2 + dp[i-1];if(pre - 1 >=0 ){dp[i] += dp[pre-1];}}}res = Math.max(res,dp[i]);}return res;}
}
3- ACM 实现
import java.util.Scanner;public class longestKH {public static int longestS(String str){int len = str.length();// 定义dpint[] dp = new int[len];int res = 0;// 递推// 当前为右括号// 求解 pre = i - dp[i-1] -1;// 如果 pre>=0 && s.charAt(pre) == '(' {dp[i] = 2 + dp[i-1];}// 3. 初始化// 4.遍历for(int i = 1 ; i < len;i++){if(str.charAt(i) == ')'){int preIndex = i - dp[i-1] - 1;if(preIndex>=0 && str.charAt(preIndex) == '('){dp[i] = 2 + dp[i-1];if(preIndex-1>=0){dp[i] += dp[preIndex-1];}}res = Math.max(res,dp[i]);}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();System.out.println("结果是"+longestS(input));}
}