# # Leetcode 第67场双周赛题解

## # Problem A - 找到和最大的长度为 K 的子序列 (opens new window)

### # 方法一：排序

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

class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
return [nums[i] for i in sorted([x[1] for x in sorted([(num, i) for i, num in enumerate(nums)])[-k:]])]

1
2
3

## # Problem B - 适合打劫银行的日子 (opens new window)

### # 方法一：动态规划

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

class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& security, int time) {
int n = security.size();
vector<int> l(n), r(n);
for (int i = 1; i < n; ++i)
if (security[i] <= security[i - 1])
l[i] = l[i - 1] + 1;
for (int i = n - 2; i >= 0; --i)
if (security[i] <= security[i + 1])
r[i] = r[i + 1] + 1;
vector<int> ans;
for (int i = 0; i < n; ++i)
if (l[i] >= time && r[i] >= time)
ans.emplace_back(i);
return ans;
}
};

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

## # Problem C - 引爆最多的炸弹 (opens new window)

### # 方法一：BFS或DFS

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

using ll = long long;

ll dis(int x1, int y1, int x2, int y2) {
return 1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2);
}

class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
for (int i = 0; i < n; ++i) {
auto &p = bombs[i];
for (int j = 0; j < n; ++j) {
auto &q = bombs[j];
if (dis(p[0], p[1], q[0], q[1]) <= 1LL * p[2] * p[2])
}
}

int ans = 1;
for (int i = 0; i < n; ++i) {
vector<bool> vis(n);
vis[i] = true;
queue<int> q;
q.push(i);
int cnt = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
cnt++;
vis[v] = true;
q.push(v);
}
}
}
ans = max(ans, cnt);
}

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

### # 方法二：位优化Floyd

• 时间复杂度$\mathcal{O}(N^3/W)$，其中$W$为字长。
• 空间复杂度$\mathcal{O}(N^2)$

using ll = long long;
using bs = bitset<100>;

ll dis(int x1, int y1, int x2, int y2) {
return 1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2);
}

class Solution {
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
vector<bs> d(n);
for (int i = 0; i < n; ++i) {
d[i].set(i);
auto &p = bombs[i];
for (int j = 0; j < n; ++j) {
auto &q = bombs[j];
if (dis(p[0], p[1], q[0], q[1]) <= 1LL * p[2] * p[2])
d[i].set(j);
}
}

for (int mid = 0; mid < n; ++mid)
for (int s = 0; s < n; ++s) {
if (d[s][mid])
d[s] |= d[mid];
}

int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, (int)d[i].count());

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

## # Problem D - 序列顺序查询 (opens new window)

### # 方法一：平衡树

• 插入和查询的时间复杂度都为$\mathcal{O}(\log N)$
• 空间复杂度$\mathcal{O}(N)$

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

class SORTracker {
ordered_set<pair<int, string>> s;
int counter = 0;
public:
SORTracker() {}

void add(string name, int score) {
s.insert(make_pair(-score, name));
}

string get() {
return s.find_by_order(counter++)->second;
}
};

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

### # 方法二：双set

• 插入的时间复杂度都为$\mathcal{O}(\log N)$，查询的时间复杂度在均摊意义下为$\mathcal{O}(\log N)$
• 空间复杂度$\mathcal{O}(N)$

class SORTracker {
set<pair<int, string>, greater<>> s1;
set<pair<int, string>> s2;
int counter = 0;
public:
SORTracker() {}

void add(string name, int score) {
s1.emplace(-score, name);
if (*s1.begin() > *s2.begin()) {
s2.insert(*s1.begin());
s1.erase(s1.begin());
}
}

string get() {
counter++;
while (s1.size() > counter) {
s2.insert(*s1.begin());
s1.erase(s1.begin());
}
while (s1.size() < counter) {
s1.insert(*s2.begin());
s2.erase(s2.begin());
}
return s1.begin()->second;
}
};

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