当前位置: 首页> 房产> 政策 > 加盟项目_装饰设计公司属于什么行业_seo快排_百度号码认证平台取消标记

加盟项目_装饰设计公司属于什么行业_seo快排_百度号码认证平台取消标记

时间:2025/7/9 2:14:13来源:https://blog.csdn.net/weixin_47894469/article/details/147090161 浏览次数:0次
加盟项目_装饰设计公司属于什么行业_seo快排_百度号码认证平台取消标记

错误解法:暴力解法,判断每一个字符的最长有效括号

class Solution {public int longestValidParentheses(String s) {Deque<Character> stack = new LinkedList<>();int n = s.length();int max= 0;int curr=0;for(int i=0;i<n;i++){if(s.charAt(i)=='('){stack.push(s.charAt(i));}if(s.charAt(i)==')'){if(!stack.isEmpty()&&stack.peek()=='('){stack.pop();curr+=2;max=Math.max(max,curr);}else{curr=0;if(!stack.isEmpty()){stack.clear();}}}}return max;}
}

错误原因:当我们判断到i=2时,无法清除curr=0

在这里插入图片描述

解法一:(动态规划)①定义:dp[i]表示下标为i结尾的最长有效括号数,dp[n] ②初始状态:dp[i]=0 ③状态转移方程

在这里插入图片描述

class Solution {public int longestValidParentheses(String s) {// 定义:dp[i]表示下标为i结尾的最长有效括号数,dp[n]// 初始状态:dp[i]=0// 状态转移方程:int n = s.length();int[] db = new int[n]; // db[i]表示以下标i结尾的最长有效括号int max= 0;for(int i=1;i<n;i++){if(s.charAt(i)==')'){// ++时,以2为单位,只要考虑‘)’if(s.charAt(i-1)=='('){// [i-1,i]是有效的,由于要求连续性,只要考虑i-2即可db[i] = (i-2>=0?db[i-2]:0)+2;}else{// 如果i的前一个不为‘(’,可能是已经和别人配对了// 要找已经配对前的是否是‘(’if(i-db[i-1]>0 && s.charAt(i-db[i-1]-1)=='('){// db[i] = (i-db[i-1]-1>=0?db[i-db[i-1]-1]:0)+2;// 要加上db[i-1]// 是i-db[i-1]-2而不是i-db[i-1]-1,已经用i-db[i-1]-1配对了,要看i-db[i-1]-2是否连续db[i] = db[i-1] + ((i-db[i-1]-2)>=0?db[i-db[i-1]-2]:0)+2;}}}max = Math.max(max, db[i]);}return max;}
}

注意:

  • 动态规划要考虑:dp代表什么?dp初始状态?dp动态转移方程?
  • 考虑的是以下标i字符结尾的最长有效括号的长度,所以要在过程中记录最大值max
关键字:加盟项目_装饰设计公司属于什么行业_seo快排_百度号码认证平台取消标记

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: