【未完成】7-8 最长有效括号串 (20 分)13分
- 2019 年 11 月 8 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/101473397
7-8 最长有效括号串 (20 分)
给定一个只含左右小括号的括号串序列exp，找出其中最长的有效括号串。
输入格式:
输入一个只含左右小括号的括号字符串，以换行结束。
输出格式:
输出其中最长的有效括号串。输出的每个括号之后均有空格。
输入样例:
())(()())
输出样例:
在这里给出相应的输出。例如：
( ( ) ( ) )
挂掉的代码
#include<iostream> using namespace std; int main(){ string s; char c; while(c!='n'){ c=getchar(); if(c=='('||c==')'){ s+=c; } } int max=-1; int num=0; int maxid=0; for(int i=0;i<s.length();i++){ string s2=s.substr(i); int flag=0; for(int l=0;l<s2.length();l++){ if(s2[l]=='('){ flag++; }else{ flag--; if(flag==0){ if(num>max){ maxid=i; max=num; } } if(flag<0){break;} num+=2; } } if(flag>0){ num=0; } if(num>max){ maxid=i; max=num; }num=0; //cout<<maxid<<max<<endl; } int k=0; for(int i=0;i<max&&max>1;i++){ cout<<s[maxid+i]<<" "; } cout<<endl; return 0; }
这道题刚好是LeetCode的原题
https://leetcode-cn.com/problems/longest-valid-parentheses/
查到的一种力扣的解法
class Solution { public: int longestValidParentheses(string s) { int ans = 0; int idx = 0; stack<pair<char, int>> sk; sk.push(make_pair<char, int>('b', 0)); for (char c : s){ idx++; if (c == '(') sk.push(make_pair(c, idx)); else{ pair<char, int> p = sk.top(); if (p.first == '('){ sk.pop(); ans = max(ans, idx - sk.top().second); } else{ assert(p.first == 'b'); sk.top().second = idx; } } } return ans; } };
