首页 > 代码库 > [Jobdu] 题目1337：寻找最长合法括号序列

[Jobdu] 题目1337：寻找最长合法括号序列

2024-07-16 12:18:42   225人阅读

题目描述：
给你一个长度为N的，由’(‘和’)’组成的括号序列，你能找出这个序列中最长的合法括号子序列么？合法括号序列的含义便是，在这个序列中，所有的左括号都有唯一的右括号匹配；所有的右括号都有唯一的左括号匹配。例如：((()))()()便是一个长度为10的合法括号序列，而(()))( 则不是。
需要你求解的是，找出最长的合法括号子序列的长度，同时找出具有这样长度的序列个数。
输入：
测试数据包括多个，每个测试数据包含两行：
第一行为一个整数N，其中N不会超过10^6。
第二行为一个长度为N的字符串，这个字符串由左括号‘(‘和右括号‘)‘组成。
输出：
对应每个测试案例，输出一行，其中包含两个整数，分别代表最长合法括号序列的长度和个数，中间由空格隔开。若没有合法的子序列存在，则返回0 1。
样例输入：
6(())()3))(
样例输出：
6 10 1

用一个bool型的数组来标记匹配情况。

 1 #include <iostream> 2 #include <stack> 3 #include <string> 4 #include <cstring> 5 using namespace std; 6   7 int n; 8 string s; 9  10 void getRes() {11     bool a[s.length()];12     memset(a, false, s.length());13     stack<int> st;14     for (int i = 0; i < s.length(); ++i) {15         if (s[i] == ‘(‘) {16             st.push(i);17         } else {18             if (!st.empty()) {19                 a[i] = true;20                 a[st.top()] = true;21                 st.pop();22             }23         }24     }25  26     int max = 0, cnt = 1, tmp = 0;27     for (int i = 0; i < s.length(); ++i) {28         if (a[i]) {29             ++tmp;30         } else {31             tmp = 0;32         }33         if (max == tmp && max != 0) {34             ++cnt;35         } else if (max < tmp) {36             max = tmp;37             cnt = 1;38         }39     }40     cout << max << " " << cnt << endl;41 }42  43 int main() {44     while (cin >> n) {45         cin >> s;46         getRes();47     }48     return 0;49 }50  51 /**************************************************************52     Problem: 133753     User: hupo25054     Language: C++55     Result: Accepted56     Time:310 ms57     Memory:7604 kb58 ****************************************************************/

 


联系
我们