# # Leetcode 第224场周赛题解

## # Problem A - 可以形成最大正方形的矩形数目 (opens new window)

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

class Solution:
def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
maxlen = max(min(l, w) for l, w in rectangles)
return sum(1 for l, w in rectangles if min(l, w) == maxlen)

1
2
3
4

## # Problem B - 同积元组 (opens new window)

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

class Solution:
def tupleSameProduct(self, nums: List[int]) -> int:
n = len(nums)
cnt = collections.Counter(nums[i] * nums[j] for i in range(n) for j in range(i + 1, n))
return sum(4 * value * (value - 1) for value in cnt.values())

1
2
3
4
5

## # Problem C - 重新排列后的最大子矩阵 (opens new window)

• 时间复杂度$\mathcal{O}(MN\log N)$，其中$M$是矩阵的行数，$N$是矩阵的列数。
• 空间复杂度$\mathcal{O}(MN)$

class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
m = len(matrix)
n = len(matrix[0])
f = [[0] * m for _ in range(n)]
for col in range(n):
for row in range(m - 1, -1, -1):
if matrix[row][col] == 1:
f[col][row] = 1
if row + 1 < m:
f[col][row] += f[col][row + 1]
ans = 0
for row in range(m):
g = [f[col][row] for col in range(n)]
g.sort(reverse=True)
for i in range(n):
ans = max(ans, g[i] * (i + 1))
return ans


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

## # Problem D - 猫和老鼠 II (opens new window)

### # 方法一：增加时间维，将状态图变为DAG

• 时间复杂度$\mathcal{O(n^3m^3)}$，因为总状态数为$n^2m^2T$，其中$T=2nm$

class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
rows = len(grid)
cols = len(grid[0])
print('\n'.join(grid))

def neighbors(pos, step):
r, c = pos
yield (r, c)
for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
for k in range(1, step + 1):
nr = r + k * dr
nc = c + k * dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols or grid[nr][nc] == '#':
break
yield (nr, nc)

for i in range(rows):
for j in range(cols):
if grid[i][j] == 'C':
cat = (i, j)
if grid[i][j] == 'M':
mouse = (i, j)
if grid[i][j] == 'F':
food = (i, j)

@functools.lru_cache(None)
def solve(mouse, cat, turn):
if mouse == cat or cat == food or turn > 2 * rows * cols:
return False
if mouse == food:
return True
if turn % 2 == 0:
for mouse_nxt in neighbors(mouse, mouseJump):
if solve(mouse_nxt, cat, turn + 1):
return True
return False
else:
for cat_nxt in neighbors(cat, catJump):
if not solve(mouse, cat_nxt, turn + 1):
return False
return True

return solve(mouse, cat, 0)

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

### # 方法二：使用变形拓扑排序，从确定结果的状态逆向求解

• 时间复杂度$\mathcal{O}(V+E)=\mathcal{O}(n^2m^2(m+n))$

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

class Solution {
int n;

int encode(int c, int m, int m_move) {
return 2 * (c * n + m) + m_move;
}

tuple<int, int, int> decode(int code) {
return {code / (2 * n), code % (2 * n) / 2, code % 2};
}
public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
int rows = grid.size(), cols = grid[0].size();
n = rows * cols;
int cat, mouse, food;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == '#')
continue;
int u = i * cols + j;
if (grid[i][j] == 'C')
cat = u;
if (grid[i][j] == 'M')
mouse = u;
if (grid[i][j] == 'F')
food = u;
for (int k = 0; k < 4; ++k) {
for (int d = 1; d <= max(catJump, mouseJump); ++d) {
int ni = i + dy[k] * d, nj = j + dx[k] * d;
if (ni < 0 || ni >= rows || nj < 0 || nj >= cols || grid[ni][nj] == '#')
break;
int v = ni * cols + nj;
if (d <= catJump)
if (d <= mouseJump)
}
}
}

int max_state = n * n * 2;
vector<int> result(max_state), in_degree(max_state);
queue<int> q;

auto assign_state = [&](int c, int m, int m_move, int state) {
int code = encode(c, m, m_move);
result[code] = state;
q.emplace(code);
};

for (int i = 0; i < n; ++i) {
if (i != food) {
assign_state(i, i, 1, -1);
assign_state(food, i, 1, -1);
assign_state(i, food, 0, -1);
}
}

for (int i = 0; i < max_state; ++i) {
auto [c, m, m_move] = decode(i);
if (m_move) {
for (int nm : madj[m]) {
int pre = encode(c, nm, 0);
in_degree[i]++;
}
} else {
for (int nc : cadj[c]) {
int pre = encode(nc, m, 1);
in_degree[i]++;
}
}
}

while (!q.empty()) {
int curr = q.front();
q.pop();
auto [c, m, m_move] = decode(curr);
for (int pre : adj[curr]) {
in_degree[pre]--;
if (result[pre] != 0)
continue;
if (result[curr] == -1) {
result[pre] = 1;
q.emplace(pre);
} else if (in_degree[pre] == 0) {
result[pre] = -1;
q.emplace(pre);
}
}
}

return result[encode(cat, mouse, 1)] == 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
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