全栈网站开发,兰州市做网站的公司,免费建设dj网站,做ptt网站目录 1- 思路题目识别动态规划 2- 实现⭐32. 最长有效括号——题解思路 3- ACM 实现 原题链接#xff1a;32. 最长有效括号 1- 思路
题目识别
识别1 #xff1a;给定一个字符串 s #xff0c;求解 s 中的最长有效括号
动态规划
动态规划五部曲
递推公式难如果遇到了 s.… 目录 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(len0){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] 2dp[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(pre0 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;// 如果 pre0 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(preIndex0 str.charAt(preIndex) (){dp[i] 2 dp[i-1];if(preIndex-10){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));}
}
