网站建设对电子商务的作用,家庭装修设计软件哪个好用,什么为网站建设提供基础素材,dw如何做商业网站输入#xff1a;一个字符串s#xff0c;只包含字符(和) 输出#xff1a;一个整数#xff0c;表示最长括号匹配子串的长度。 规则#xff1a;括号匹配的字符是指每有一个‘(’字符就有对应的‘)’。 其他 情况都是无效的。 暴力算法分析#xff1a;取字符串s的每一个子串一个字符串s只包含字符(和) 输出一个整数表示最长括号匹配子串的长度。 规则括号匹配的字符是指每有一个‘(’字符就有对应的‘)’。 其他 情况都是无效的。 暴力算法分析取字符串s的每一个子串然后用 stack判断字符串是否括号匹配的字符串。时间复杂度O(n3)O(n^3)O(n3)。 public int longestValidParentheses(String s) {int n s.length();int maxlength 0;for(int i0;in;i){for(int ji1;jn;j){if(validate(s.substring(i,j1))){maxlength Math.max(maxlength,j1-i);}}}return maxlength;}private boolean validate(String s ){StackCharacter stack new StackCharacter();for(int i0;is.length();i){char ch s.charAt(i);if(!stack.isEmpty()){if(ch) stack.peek()(){stack.pop();}else{stack.push(s.charAt(i));}}else{stack.push(s.charAt(i));}}return stack.isEmpty();}动态规划思路用dp[i] 以第i个元素为结尾的子串的最长括号匹配子串的长度。 dp初始化为0。 显然括号匹配子串一定以)结尾那么如果s[i]’(’那么dp[i]0。 如果s[i]’)‘并且s[i-1]’(’也就是字符串形如’…()’那么dp[i] 2 dp[i-2]。
如果s[i]’)‘并且s[i-1]’)’也就是字符串形如’…))’如果在i-1位置之前有对应第i个元素对应的(字符那么字符串形如’…(有效子串si−1s_{i-1}si−1)’那么(的下标应该是i-1-dp[i-1]。 如果s[i-dp[i-1]-1]’(’那么dp[i] dp[i-1]2 dp[i-dp[i-1]-2]。因为(字符前面可能还有字符其长度为dp[i-dp[i-1]-2]。 例如s’(()))(())’在计算dp[7]的时候因为dp[6]2所以与其对应的(位置在7-1-dp[7-1]4。从0到3还是一个括号匹配字符长度为dp[3]。所以dp[7] dp[6]2dp[3]8。
0123456700240028public int longestValidParenthesesV2(String s) {int n s.length();int[] dp new int[n];int max 0;for(int i 1;in;i){if(s.charAt(i))){if(s.charAt(i-1) (){dp[i] (i2?dp[i-2]:0)2;}else if(i-dp[i-1] 0 s.charAt(i-dp[i-1]-1)(){dp[i] dp[i-1] (i-dp[i-1]-20? dp[i-dp[i-1]-2]:0) 2;}}max Math.max(max, dp[i]);}return max;}双指针思路用两个指针left、right分别表示 遇到的 左括号、右括号的个数。 首先从左向右遍历遇到(left遇到)right。当leftright的时候括号匹配长度2*left。记录遇到的最大长度。如果rightleft则说明子串无效重置为0。 其次从右向左遍历一次。 最后得到最大长度。 public int longestValidParenthesesV3(String s) {int n s.length();int max 0;int left0,right 0;for(int i0;in;i){if(s.charAt(i) (){left;}else{right;}if(left right){max Math.max(max, 2*left);}else if(rightleft){left right 0;}}left right 0;for(int in-1;i0;i--){if(s.charAt(i) (){left;}else{right;}if(left right){max Math.max(max, 2*left);}else if(leftright){left right 0;}}return max;}参考链接力扣官方
