# # Leetcode 第197场周赛题解

## # Problem A - 好数对的数目 (opens new window)

class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0;
int n = nums.size();
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans += nums[i] == nums[j];
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0;
vector<int> cnt(101);
for (int i : nums)
cnt[i]++;
for (int i = 1; i <= 100; ++i)
ans += cnt[i] * (cnt[i] - 1) / 2;
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12

## # Problem B - 仅含 1 的子串数 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int numSub(string s) {
s += "0";
ll curr = 0, ans = 0;
for (char c : s) {
if (c == '1')
curr++;
else {
ans += curr * (curr + 1) / 2;
ans %= MOD;
curr = 0;
}
}
return ans;
}
};

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

## # Problem C - 概率最大的路径 (opens new window)

const double eps = 1e-8;

class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> prob(n);
prob[start] = 1;
for (int i = 0; i < edges.size(); ++i) {
int u = edges[i][0], v = edges[i][1];
double p = succProb[i];
}
priority_queue<pair<double, int>> pq;
vector<bool> vis(n);
pq.push({1, start});
while (!pq.empty()) {
auto top = pq.top();
double p = top.first;
int u = top.second;
pq.pop();
if (vis[u])
continue;
vis[u] = true;
if (p < eps)
continue;
for (auto edge : adj[u]) {
int v = edge.first;
double now = p * edge.second;
if (prob[v] < now) {
prob[v] = now;
pq.push({prob[v], v});
}
}
}

return prob[end];
}
};

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

## # Problem D - 服务中心的最佳位置 (opens new window)

const double eps = 1e-8;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

double calc(double ax, double ay, double bx, double by) {
double dx = bx - ax, dy = by - ay;
return sqrt(dx * dx + dy * dy);
}

class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
int n = positions.size();
double x = 0, y = 0;
for (auto v : positions) {
x += v[0];
y += v[1];
}
x /= n, y /= n;
auto dist = [&](double cx, double cy) {
double ans = 0;
for (auto v : positions)
ans += calc(cx, cy, v[0], v[1]);
return ans;
};
double d = dist(x, y);
double step = 100.0;
int done = 0;
while (step > eps) {
done = 0;
for (int i = 0; i < 4; ++i) {
double nx = x + step * dx[i];
double ny = y + step * dy[i];
double t = dist(nx, ny);
if (t < d) {
d = t;
x = nx;
y = ny;
done = 1;
break;
}
}
if (!done)
step /= 2;
}

return d;
}
};

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