# # Ad Hoc问题

## # 练习题

### #LC1190 - 反转每对括号间的子串 (opens new window)


class Solution {
public:
string reverseParentheses(string s) {
int n = s.size();
vector<int> pair(n, -1);
stack<int> st;
int p = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(')
p++, st.push(i);
if (s[i] == ')') {
int j = st.top();
pair[i] = j;
pair[j] = i;
st.pop();
}
}
int c = n - 2 * p;
string ans;
int pos = 0;
bool right = true;
while (ans.size() < c) {
if (s[pos] == '(' || s[pos] == ')') {
pos = pair[pos];
right = !right;
} else {
ans.push_back(s[pos]);
}
if (right)
pos++;
else
pos--;
}
return ans;
}
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

### #BS679 - Delete from the ends and Reinsert to Target (opens new window)

#include "solution.hpp"
using namespace std;

class Solution {
public:
int solve(string s, string t) {
int n = s.size();
vector<vector<int>> nxt(n + 1, vector<int>(26, -1));
vector<int> c(26, -1);
for (int i = n - 1; i >= 0; --i) {
nxt[i + 1] = c;
c[t[i] - 'a'] = i + 1;
}
nxt[0] = c;
int hi = 0;
for (int i = 0; i < n; ++i) {
int p = 0, now = 0;
while (i + p < n && nxt[now][s[i + p] - 'a'] != -1) {
now = nxt[now][s[i + p] - 'a'];
p++;
}
hi = max(hi, p);
}
return n - hi;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

### #Kattis - Juggling Patterns (opens new window)

import sys

for raw_line in sys.stdin:
line = raw_line.strip()
tot = sum([int(i) for i in line])
n = len(line)
if tot % n != 0:
print('{}: invalid # of balls'.format(line))
continue
balls = tot // n
s = set()
ok = True
for i, c in enumerate(line):
s.add((i + int(c)) % n)
if len(s) == n:
print('{}: valid with {} balls'.format(line, balls))
else:
print('{}: invalid pattern'.format(line))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18