本题有非常直接的解法,根据输入先将括号字符串还原,再对还原后的括号字符串进行计算,但效率不高,需要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>
3using namespace std;
4
5class Info
6{
7public:
8 int left;
9 int have;
10};
11
12template <class T>
13class Stack
14{
15private:
16 vector<T> v;
17public:
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
41int _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
肖羽思 阅读(646)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ