# # Leetcode 第285场周赛题解

## # Problem A - 由单个字符重复的最长子字符串 (opens new window)

### # 方法一：去重后计数

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def countHillValley(self, nums: List[int]) -> int:
s = []
for num in nums:
if len(s) == 0 or num != s[-1]:
s.append(num)
n = len(s)
print(s)
ans = 0
for i in range(1, n - 1):
l = i - 1
r = i + 1
if (s[l] < s[i] and s[r] < s[i]) or (s[l] > s[i] and s[r] > s[i]):
ans += 1
return ans

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

## # Problem B - 统计道路上的碰撞次数 (opens new window)

### # 方法一：脑筋急转弯

• 时间复杂度 $\mathcal{O}(|S|)$
• 空间复杂度 $\mathcal{O}(1)$

class Solution {
public:
int countCollisions(string directions) {
string s = directions;
int st = 0;
for (char ch : directions)
if (ch == 'S')
st++;
int n = s.size();
int l = 0;
while (l < n && s[l] == 'L')
l++;
int r = n - 1;
while (r >= 0 && s[r] == 'R')
r--;
return max(0, r - l + 1 - st);
}
};

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

## # Problem C - 射箭比赛中的最大得分 (opens new window)

### # 方法一：贪心+枚举

• 时间复杂度 $\mathcal{O}(N\cdot2^N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution {
public:
vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
int n = aliceArrows.size();
int best = 0;
int best_state = 0;
for (int i = 1; i < (1 << n); ++i) {
int sum = 0, score = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
sum += aliceArrows[j] + 1, score += j;
}
if (sum <= numArrows && score > best)
best = score, best_state = i;
}
int tot = numArrows;
vector<int> bobArrows(n);
for (int j = 0; j < n; ++j)
if (best_state & (1 << j))
bobArrows[j] = aliceArrows[j] + 1, tot -= aliceArrows[j] + 1;
bobArrows[n - 1] += tot;
return bobArrows;
}
};

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

## # Problem D - 由单个字符重复的最长子字符串 (opens new window)

### # 方法一：维护每个字母的连续段

• 时间复杂度 $\mathcal{O}(N\log N + Q(\log N+|\Sigma|))$
• 空间复杂度 $\mathcal{O}(N+Q)$

struct SegPool {
set<pair<int, int>> segs;
multiset<int> length;

void insert_seg(int l, int r) {
segs.emplace(l, r);
length.emplace(r - l + 1);
}

int max_len() {
if (segs.empty())
return 0;
return *length.rbegin();
}

void remove_at(int id) {
auto it = segs.lower_bound(make_pair(id, INT_MAX));
it--;
auto [l, r] = *it;
segs.erase(it);
length.erase(length.find(r - l + 1));
if (l < id)
segs.emplace(l, id - 1);
length.emplace(id - l);
if (id < r)
segs.emplace(id + 1, r);
length.emplace(r - id);
}

void insert_at(int id) {
auto it = segs.lower_bound(make_pair(id, INT_MAX));
int l = id, r = id;

vector<pair<int, int>> to_remove;
if (it != segs.end() && it->first == id + 1) {
auto [rl, rr] = *it;
to_remove.emplace_back(rl, rr);
length.erase(length.find(rr - rl + 1));
r = rr;
}

if (it != segs.begin() && prev(it)->second == id - 1) {
auto [ll, lr] = *prev(it);
to_remove.emplace_back(ll, lr);
length.erase(length.find(lr - ll + 1));
l = ll;
}

for (auto p : to_remove)
segs.erase(p);
segs.emplace(l, r);
length.emplace(r - l + 1);
}
};

class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
vector<SegPool> pools(26);

int n = s.size();
for (char c = 'a'; c <= 'z'; ++c) {
vector<int> pos;
for (int i = 0; i < n; ++i)
if (s[i] == c)
pos.push_back(i);
int l = -2, r = -2;
for (int p : pos) {
if (p > r + 1) {
if (l != -2)
pools[c - 'a'].insert_seg(l, r);
l = r = p;
} else
r++;
}
if (l != -2)
pools[c - 'a'].insert_seg(l, r);
}

int q = queryCharacters.size();
int last = 0;
for (int j = 0; j < 26; ++j)
last = max(last, pools[j].max_len());

vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int ci = queryCharacters[i] - 'a';
int id = queryIndices[i];
if (s[id] - 'a' == ci) {
ans[i] = last;
continue;
}
pools[s[id] - 'a'].remove_at(id);
pools[ci].insert_at(id);
s[id] = queryCharacters[i];
for (int j = 0; j < 26; ++j)
last = ans[i] = max(ans[i], pools[j].max_len());
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102