# # Leetcode 第206场周赛题解

## # Problem A - 二进制矩阵中的特殊位置 (opens new window)

class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int ans = 0;
int n = mat.size(), m = mat[0].size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (!mat[i][j])
continue;
bool ok = true;
for (int k = 0; k < n; ++k)
if (k != i && mat[k][j]) {
ok = false;
break;
}
for (int k = 0; k < m; ++k)
if (k != j && mat[i][k]) {
ok = false;
break;
}
ans += ok;
}
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

## # Problem B - 统计不开心的朋友 (opens new window)

class Solution {
public:
int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
vector<vector<int>> mat(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j)
mat[i][preferences[i][j]] = n - j;
vector<bool> unhappy(n);
for (auto p : pairs)
for (auto q: pairs) {
if (p == q)
continue;
int x = p[0], y = p[1], u = q[0], v = q[1];
if (mat[x][u] > mat[x][y] && mat[u][x] > mat[u][v])
unhappy[x] = true;
if (mat[x][v] > mat[x][y] && mat[v][x] > mat[v][u])
unhappy[x] = true;
if (mat[y][u] > mat[y][x] && mat[u][y] > mat[u][v])
unhappy[y] = true;
if (mat[y][v] > mat[y][x] && mat[v][y] > mat[v][u])
unhappy[y] = true;
}
int ans = 0;
for (int i : unhappy)
ans += i;
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

## # Problem C - 连接所有点的最小费用 (opens new window)

#define INF 0x3f3f3f3f

class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
int ans = 0;
vector<bool> vis(n);
vector<int> min_dist(n, INF);
min_dist[0] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
int gmin = INF;
for (int j = 0; j < n; ++j) {
if (!vis[j] && min_dist[j] <= gmin) {
gmin = min_dist[j];
u = j;
}
}
ans += gmin;
vis[u] = true;
for (int j = 0; j < n; ++j)
if (!vis[j]) {
int new_dist = abs(points[j][0] - points[u][0]) + abs(points[j][1] - points[u][1]);
min_dist[j] = min(min_dist[j], new_dist);
}
}
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

## # Problem D - 检查字符串是否可以通过排序子字符串得到另一个字符串 (opens new window)

class Solution {
public:
bool isTransformable(string s, string t) {
vector<int> cs(10), ct(10);
for (char c : s)
cs[c - '0']++;
for (char c : t)
ct[c - '0']++;
for (int i = 0; i < 10; ++i)
if (cs[i] != ct[i])
return false;
vector<vector<vector<int>>> rs(10);
vector<int> fs(10);
for (int i = 0; i < s.size(); ++i) {
int c = s[i] - '0';
rs[c].push_back(fs);
fs[c]++;
}
vector<int> ft(10);
for (int i = 0; i < t.size(); ++i) {
int c = t[i] - '0';
int idx = ft[c];
for (int j = 0; j < c; ++j) {
if (ft[j] < rs[c][idx][j])
return false;
}
ft[c]++;
}
return true;
}
};

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