# # Leetcode 第274场周赛题解

## # Problem A - 检查是否所有 A 都在 B 之前 (opens new window)

### # 方法一：模拟

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

class Solution:
def checkString(self, s: str) -> bool:
return s.rfind('a') < (len(s) if s.find('b') == -1 else s.find('b'))

1
2
3

## # Problem B - 银行中的激光束数量 (opens new window)

### # 方法一：模拟

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

class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
last = 0
ans = 0
for row in bank:
devices = row.count('1')
if devices > 0:
ans += last * devices
last = devices
return ans

1
2
3
4
5
6
7
8
9
10

class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
return functools.reduce(lambda x, row: (rc:=row.count('1'), x[1] + x[2] * rc, rc if rc > 0 else x[2]), bank, (0, 0, 0))[1]

1
2
3

## # Problem C - 摧毁小行星 (opens new window)

### # 方法一：贪心

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

class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
asteroids.sort()
for asteroid in asteroids:
if mass < asteroid:
return False
mass += asteroid
return True

1
2
3
4
5
6
7
8

class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
return functools.reduce(lambda x, asteroid: (x[0], False) if not x[1] or x[0] < asteroid else (x[0] + asteroid, True), sorted(asteroids), (mass, True))[1]

1
2
3

## # Problem D - 参加会议的最多员工数 (opens new window)

### # 方法一：DFS

1. 所有被安排的员工构成一个环：A->B->C->D->…->A
2. 所有被安排的员工为若干个组，每个组的结构为：A->B->…->C↔D<-E<-…<-F

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

class Solution {
int n, max_loop, from_pairs;
vector<int> color, dep;
vector<pair<int, int>> pairs;
vector<vector<int>> rev;

void dfs(int u) {
color[u] = 1;

for (int v : rev[u]) {
if (!color[v]) {
dep[v] = dep[u] + 1;
dfs(v);
} else if (color[v] == 1) {
int loop = dep[u] - dep[v] + 1;
max_loop = max(max_loop, loop);
if (loop == 2)
pairs.emplace_back(u, v);
}
}

color[u] = 2;
}

int dfs2(int u, int p, int d) {
int max_depth = d;

for (int v : rev[u]) {
if (v != p)
max_depth = max(max_depth, dfs2(v, p, d + 1));
}

return max_depth;
}

public:
int maximumInvitations(vector<int>& favorite) {
n = favorite.size();
color = vector<int>(n);
dep = vector<int>(n);
max_loop = 0;

rev = vector<vector<int>>(n);
for (int i = 0; i < n; ++i)
rev[favorite[i]].emplace_back(i);

for (int i = 0; i < n; ++i) {
if (!color[i])
dfs(i);
}

from_pairs = 0;
for (auto &[u, v] : pairs) {
from_pairs += dfs2(u, v, 1);
from_pairs += dfs2(v, u, 1);
}

return max(max_loop, from_pairs);
}
};

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