本文主要是介绍32力扣 最长有效括号,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
dp方法:
class Solution {
public:int longestValidParentheses(string s) {int n=s.size();vector<int> dp(n,0);if(n==0 || n==1) return 0;if(s[0]=='(' && s[1]==')'){dp[1]=2;}for(int i=2;i<n;i++){if(s[i]==')'){if(s[i-1]=='('){dp[i]=dp[i-2]+2;}else if(s[i-1]==')'){if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='('){if(i-dp[i-1]-2>=0)dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];else dp[i]=dp[i-1]+2;}}}}return *max_element(dp.begin(), dp.end());}
};
连续1方法:
class Solution {
public:int longestValidParentheses(string s) {int n=s.size();vector<pair<char,int>> stack;vector<int> tmp(n,0);for(int i=0;i<n;i++){if(stack.empty()){stack.push_back(make_pair(s[i],i));}else{if(stack.back().first=='(' && s[i]==')'){tmp[i]=tmp[stack.back().second]=1; stack.pop_back();}else {stack.push_back(make_pair(s[i],i));}}}int count=0;int count_max=0;for(int i=0;i<n;i++){if(tmp[i]==1){count++;}else{count_max=max(count_max,count);count=0;}}count_max=max(count_max,count);return count_max;}
};
这篇关于32力扣 最长有效括号的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!