本题有非常直接的解法,根据输入先将括号字符串还原,再对还原后的括号字符串进行计算,但效率不高,需要n2+n的时间复杂度,其实可以用线性扫描在O(n)的时间内解决,具体思路如下:
在扫描的时候,利用一个栈保存已有的左括号信息(包括剩下几个未匹配的左括号与已经匹配左括号的个数),在扫描到输入j的时候,有以下三种情况(设i为j前一个输入):
1. i == j - 1;这种情况非常简单,表明新输入的右括号与自身所带的左括号匹配,直接输出1,更新栈顶元素信息.
2. i < j - 1; 这种输入表明j位置上的右括号自带了比自身所需更多的左括号,将剩余的左括号相关信息入栈保存.
3. i == j;表明位置j并没有任何自身的左括号,需要向栈中借,并更新栈相关信息.

Code
1
#include <vector>
2
#include <iostream>
3
using namespace std;
4
5
class Info
6

{
7
public:
8
int left;
9
int have;
10
};
11
12
template <class T>
13
class Stack
14

{
15
private:
16
vector<T> v;
17
public:
18
void push(const T & t)
19
{
20
v.push_back(t);
21
}
22
23
T & pop()
24
{
25
T & temp = v[v.size() - 1];
26
v.pop_back();
27
return temp;
28
}
29
30
T & top()
31
{
32
return v[v.size() - 1];
33
}
34
35
int size() const
36
{
37
return v.size();
38
}
39
};
40
41
int _tmain(int argc, _TCHAR* argv[])
42

{
43
int num;
44
cin >> num;
45
Stack<Info> s;
46
47
while(num--)
48
{
49
int n;
50
cin >> n;
51
int * parenttheses = new int[n];
52
53
for(int i = 0; i < n; ++i)
54
{
55
cin >> parenttheses[i];
56
}
57
58
Info original;
59
s.push(original);
60
61
for(int i = 0; i < n; ++i)
62
{
63
if(i == 0)
64
{
65
s.top().left = parenttheses[i] - 1;
66
s.top().have = 1;
67
cout << "1 ";
68
}
69
else
70
{
71
// except the nearby one, we still have more left parenttheses, store them into stack
72
if(parenttheses[i] - parenttheses[i - 1] > 1)
73
{
74
Info new_info;
75
new_info.have = 1;
76
new_info.left = parenttheses[i] - parenttheses[i - 1] - 1;
77
s.push(new_info);
78
cout << "1 ";
79
}
80
// the right parenttheses just pair with the nearby left one
81
else if(parenttheses[i] - parenttheses[i - 1] == 1)
82
{
83
if(i != n - 1)
84
{
85
cout << "1 ";
86
if(s.size() > 0)
87
++s.top().have;
88
}
89
else
90
{
91
cout << "1";
92
}
93
}
94
// no nearby left one exists, need to borrow from stack
95
else
96
{
97
--s.top().left;
98
++s.top().have;
99
100
// if it's not the last one
101
if(i != n - 1)
102
{
103
cout << s.top().have << " ";
104
}
105
else
106
{
107
cout << s.top().have;
108
}
109
110
if(s.top().left == 0)
111
{
112
Info last = s.pop();
113
if(s.size() != 0)
114
{
115
s.top().have += last.have;
116
}
117
}
118
}
119
}
120
if(i == n - 1)
121
cout << endl;
122
}
123
124
delete parenttheses;
125
}
126
return 0;
127
}
128
129
posted on 2009-03-24 20:29
肖羽思 阅读(655)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ