# # Leetcode 第77场双周赛题解

## # Problem A - 统计是给定字符串前缀的字符串数目 (opens new window)

### # 方法一：计数

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

class Solution:
def countPrefixes(self, words: List[str], s: str) -> int:
cnt = collections.Counter(words)
return sum(cnt[s[:i]] for i in range(1, len(s) + 1))

1
2
3
4

## # Problem B - 最小平均差 (opens new window)

### # 方法一：枚举

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

class Solution:
def minimumAverageDifference(self, nums: List[int]) -> int:
n = len(nums)
right = sum(nums)
left = 0
ans = -1
best = int(1e10)
for i in range(n):
left += nums[i]
right -= nums[i]
lavg = left // (i + 1)
ravg = right // max(1, n - i - 1)
curr = abs(lavg - ravg)
if curr < best:
ans = i
best = curr
return ans

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

## # Problem C - 统计网格图中没有被保卫的格子数 (opens new window)

### # 方法一：线性探查 * 4

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

class Solution {
public:
int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
vector<vector<int>> vis(m, vector<int>(n));
for (auto &g : guards)
vis[g[0]][g[1]] = 1;
for (auto &w : walls)
vis[w[0]][w[1]] = 2;
for (int i = 0; i < m; ++i) {
int now = 0;
for (int j = 0; j < n; ++j) {
if (vis[i][j] == 1)
now = 1;
else if (vis[i][j] == 2)
now = 0;
else if (vis[i][j] == 0 && now == 1)
vis[i][j] = 3;
}

now = 0;
for (int j = n - 1; j >= 0; --j) {
if (vis[i][j] == 1)
now = 1;
else if (vis[i][j] == 2)
now = 0;
else if (vis[i][j] == 0 && now == 1)
vis[i][j] = 3;
}
}

for (int j = 0; j < n; ++j) {
int now = 0;
for (int i = 0; i < m; ++i) {
if (vis[i][j] == 1)
now = 1;
else if (vis[i][j] == 2)
now = 0;
else if (vis[i][j] == 0 && now == 1)
vis[i][j] = 3;
}

now = 0;
for (int i = m - 1; i >= 0; --i) {
if (vis[i][j] == 1)
now = 1;
else if (vis[i][j] == 2)
now = 0;
else if (vis[i][j] == 0 && now == 1)
vis[i][j] = 3;
}
}

int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (vis[i][j] == 0)
ans++;

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

## # Problem D - 逃离火灾 (opens new window)

### # 方法一：BFS + 二分答案

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

const int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

class Solution {
public:
int maximumMinutes(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();

vector<vector<int>> days(n, vector<int>(m, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
days[i][j] = 0;
q.emplace(i, j);
}
}

while (!q.empty()) {
auto [i, j] = q.front();
q.pop();

for (int k = 0; k < 4; ++k) {
int ni = i + d[k][0], nj = j + d[k][1];
if (ni < 0 || ni >= n || nj < 0 || nj >= m ||
days[ni][nj] != -1 || grid[ni][nj] == 2)
continue;
days[ni][nj] = days[i][j] + 1;
q.emplace(ni, nj);
}
}

auto can_go = [&](int day) {
vector<vector<int>> vis(n, vector<int>(m, -1));
vis[0][0] = day;

queue<pair<int, int>> q;
q.emplace(0, 0);

while (!q.empty()) {
auto [i, j] = q.front();
q.pop();

for (int k = 0; k < 4; ++k) {
int ni = i + d[k][0], nj = j + d[k][1];
if (ni < 0 || ni >= n || nj < 0 || nj >= m ||
grid[ni][nj] == 2 ||
vis[ni][nj] != -1 ||
(days[ni][nj] != -1 &&
(vis[i][j] + 1 > days[ni][nj])))
continue;
if (vis[i][j] + 1 == days[ni][nj] && (ni != n - 1 || nj != m - 1))
continue;
vis[ni][nj] = vis[i][j] + 1;
q.emplace(ni, nj);
}
}

return vis[n - 1][m - 1] != -1;
};

int lo = 0, hi = n * m;
while (lo <= hi) {
int mid = (lo + hi) / 2;

if (can_go(mid))
lo = mid + 1;
else
hi = mid - 1;
}

if (hi == n * m) return 1e9;
return 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
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