655
九度題目1342：尋找最長合法括號序列II
題目1342：尋找最長合法括號序列II（25分）
時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：732
解決：294
題目描述：
假如給你一個由’(‘和’)’組成的一個隨機的括號序列，當然，這個括號序列肯定不能保證是左右括號匹配的，所以給你的任務便是去掉其中的一些括號，使得剩下的括號序列能夠左右括號匹配且長度最長，即最長的合法括號序列。
輸入：
測試數據包括多個，每個測試數據隻有一行，即一個隨機的括號序列，該括號序列的長度保證不超過106。
輸出：
對於每個測試案例，輸出一個整數，表示最後剩下的最長合法括號序列長度。
樣例輸入：
(())()
(()
樣例輸出：
6
2
思路：以前做過的水題...用棧模擬即可，相同的出棧，不相同繼續進棧....
AC代碼：
#include<stdio.h>
#include<string.h>
char s[1000010];
char stack[1000010];
int main()
{
int i,j,n,m,sum;
while(gets(s))
{
n=strlen(s);m=0;
sum=0;
for(i=0;i<n;i++)
{
stack[m++]=s[i];
if(m-2>=0)
{
if(stack[m-2]=='('&&stack[m-1]==')')
{
sum+=2;
m-=2;
}
}
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 12:56:29