首页 > ACM题库 > 九度OJ > 九度-1337-寻找最长合法括号序列[解题代码]
2013
12-13

九度-1337-寻找最长合法括号序列[解题代码]

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

cpp 代码如下:
#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;
				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: coder
	Language: C
	Result: Accepted
	Time:100 ms
	Memory:9704 kb
****************************************************************/


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

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }