首页 > ACM题库 > 九度OJ > 九度-1337-寻找最长合法括号序列[数据结构]
2014
02-02

九度-1337-寻找最长合法括号序列[数据结构]

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

不是新题了,栈的应用。这里用数组模拟。

#include <stdio.h>
char s[1000001];
int opt[1000001];
int stack[1000000], m, ans, l, cnt, i, last, ll;
int main() {
    int n;
    while (scanf("%d %s", &n, s) != EOF) {
        opt[0] = opt[1] = 0;
        cnt = l = ans = m = last =0;
        for (i = 1; i <= n; i++) {
            if (s[i-1] == '(') {
                stack[l++] = i;//l记录左括号个数
                opt[i] = 0;
            } else {
                if(l){
                    l--;//左括号匹配,栈弹出
                    opt[i] = opt[stack[l]-1] + 2;
                    if(s[i-2] == ')') 
                        opt[i] += opt[i-1];
                    opt[stack[l] - 1] = opt[i];
                }else
                    opt[i] = 0;
            }
            if(opt[i] > ans){
                ans = opt[i];
                cnt = 1;
            }else if(opt[i] == ans) cnt ++;
        }
        if(ans)
            printf("%d %d\n", ans, cnt);
        else
            printf("0 1\n");
 
    }
    return 0;
}
/**************************************************************
    Problem: 1337
    User: 从此醉
    Language: C
    Result: Accepted
    Time:100 ms
    Memory:9704 kb
****************************************************************/
 

 


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. […] 如果此题没有要求 相对位置不变,可以参考文章:http://www.acmerblog.com/interview-9-2427/ […]