# # Leetcode 第54场双周赛题解

## # Problem A - 检查是否区域内所有整数都被覆盖 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(NM)$，其中$M=R-L+1$
• 空间复杂度$\mathcal{O}(1)$

class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
for i in range(left, right + 1):
found = False
for l, r in ranges:
if l <= i <= r:
found = True
break
if not found:
return False
return True

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 找到需要补充粉笔的学生编号 (opens new window)

### # 方法一：贪心

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

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

class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
s = sum(chalk)
k %= s
for i, num in enumerate(chalk):
if k < num:
return i
k -= num
return -1

1
2
3
4
5
6
7
8
9

## # Problem C - 最大的幻方 (opens new window)

### # 方法一：前缀和+暴力

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

class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> rowsum(n, vector<int>(m + 1));
vector<vector<int>> colsum(m, vector<int>(n + 1));
for (int i = 0; i < n; ++i)
for (int j = 1; j <= m; ++j)
rowsum[i][j] = rowsum[i][j - 1] + grid[i][j - 1];
for (int j = 0; j < m; ++j)
for (int i = 1; i <= n; ++i)
colsum[j][i] = colsum[j][i - 1] + grid[i - 1][j];

int k = min(m, n);
for (int s = k; s >= 2; --s) {
for (int i = 0; i + s <= n; ++i)
for (int j = 0; j + s <= m; ++j) {
int sum = rowsum[i][j + s] - rowsum[i][j];
bool good = true;
for (int p = 1; p < s; ++p)
if (rowsum[i + p][j + s] - rowsum[i + p][j] != sum) {
good = false;
break;
}
if (!good)
continue;
int dsum1 = 0, dsum2 = 0;
for (int p = 0; p < s; ++p) {
if (colsum[j + p][i + s] - colsum[j + p][i] != sum) {
good = false;
break;
}
dsum1 += grid[i + p][j + p];
dsum2 += grid[i + p][j + s - 1 - p];
}
if (dsum1 != sum || dsum2 != sum)
good = false;
if (good)
return s;
}
}

return 1;
}
};

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

## # Problem D - 反转表达式值的最少操作次数 (opens new window)

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

• 我们如果要得到$0$，只需要有一边为$0$，代价为$\min(p_1,p_2)$

• 我们如果要得到$1$，需要左右两边同时为$1$，代价为$q_1+q_2$；或者将操作符变为|，同时只需要左右有一边为$1$，代价为$\min(q_1,q_2)+1$

• 我们如果要得到$0$，需要左右两边同时为$0$，代价为$p_1+p_2$；或者将操作符变为&，同时只需要左右有一边为$0$，代价为$\min(p_1,p_2)+1$
• 我们如果要得到$1$，只需要有一边为$1$，代价为$\min(q_1,q_2)$

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

class Solution:
def minOperationsToFlip(self, expression: str) -> int:
states = []
ops = []

for c in expression:
if c in '01)':
if c == '0':
states.append((0, 1))
elif c == '1':
states.append((1, 0))
else:
assert(ops[-1] == '(')
ops.pop()

if len(ops) > 0 and ops[-1] != '(':
op = ops.pop()
p2, q2 = states.pop()
p1, q1 = states.pop()
if op == '&':
states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))
else:
states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))
else:
ops.append(c)

return max(states[-1])

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