# # Leetcode 第212场周赛题解

## # Problem A - 按键持续时间最长的键 (opens new window)

• 时间复杂度$O(N)$

class Solution {
public:
char slowestKey(vector<int>& releaseTimes, string keysPressed) {
int last = 0;
char c = 'a';
int t = 0;
for (int i = 0; i < releaseTimes.size(); ++i) {
int ti = releaseTimes[i] - last;
if (ti > t || (ti == t && keysPressed[i] > c)) {
t = ti;
c = keysPressed[i];
}
last = releaseTimes[i];
}
return c;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

## # Problem B - 等差子数组 (opens new window)

• 时间复杂度$O(MN\log N)$

class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
ans = []
for li, ri in zip(l, r):
a = nums[li : ri + 1]
a.sort()
ok = True
for i in range(2, len(a)):
if a[i] - a[i - 1] != a[1] - a[0]:
ok = False
break
ans.append(ok)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

## # Problem C - 最小体力消耗路径 (opens new window)

BFS+二分答案。

• 时间复杂度$O(NM\log H_\text{max})$

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

class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int n = heights.size(), m = heights[0].size();
auto valid = [&](int th){
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m));
vis[0][0] = true;
q.emplace(0, 0);
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
if (i == n - 1 && j == m - 1)
return true;
for (int k = 0; k < 4; ++k) {
int ni = i + dy[k], nj = j + dx[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[ni][nj] || abs(heights[ni][nj] - heights[i][j]) > th)
continue;
vis[ni][nj] = true;
q.emplace(ni, nj);
}
}
return false;
};

int l = 0, r = 1e6;
while (l <= r) {
int mid = (l + r) >> 1;
if (!valid(mid))
l = mid + 1;
else
r = mid - 1;
}
return l;
}
};
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

## # Problem D - 矩阵转换后的秩 (opens new window)

• 时间复杂度$O(NM\log\max(N,M))$，瓶颈为排序。

class UnionFind {
int n;
vector<int> parent, size;

public:
UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};

class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
UnionFind uf(n * m);
for (int i = 0; i < n; ++i) {
map<int, vector<int>> mp;
for (int j = 0; j < m; ++j)
mp[matrix[i][j]].emplace_back(i * m + j);
for (auto &[num, vec] : mp) {
for (int k = 0; k + 1 < vec.size(); ++k)
uf.connect(vec[k], vec[k + 1]);
}
}
for (int j = 0; j < m; ++j) {
map<int, vector<int>> mp;
for (int i = 0; i < n; ++i)
mp[matrix[i][j]].emplace_back(i * m + j);
for (auto &[num, vec] : mp) {
for (int k = 0; k + 1 < vec.size(); ++k)
uf.connect(vec[k], vec[k + 1]);
}
}
vector<int> indegree(n * m);
for (int i = 0; i < n; ++i) {
vector<pair<int, int>> v(m);
for (int j = 0; j < m; ++j)
v[j] = make_pair(matrix[i][j], j);
sort(v.begin(), v.end());
for (int j = 0; j + 1 < m; ++j)
if (v[j].first != v[j + 1].first) {
int uu = uf.find(i * m + v[j].second);
int vv = uf.find(i * m + v[j + 1].second);
indegree[vv]++;
}
}
for (int j = 0; j < m; ++j) {
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i)
v[i] = make_pair(matrix[i][j], i);
sort(v.begin(), v.end());
for (int i = 0; i + 1 < n; ++i)
if (v[i].first != v[i + 1].first) {
int uu = uf.find(v[i].second * m + j);
int vv = uf.find(v[i + 1].second * m + j);
indegree[vv]++;
}
}
vector<int> ans(n * m, 1);
queue<int> q;
for (int i = 0; i < n * m; ++i) {
if (uf.find(i) == i && indegree[i] == 0)
q.emplace(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
ans[v] = max(ans[v], ans[u] + 1);
indegree[v]--;
if (indegree[v] == 0)
q.emplace(v);
}
}
vector<vector<int>> result(n, vector<int>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
result[i][j] = ans[uf.find(i * m + j)];
return result;
}
};
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
103
104
105
106
107