# # Leetcode 第193场周赛题解

## # Problem A - 一维数组的动态和 (opens new window)

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

1
2
3
4
5
6
7
8
9

## # Problem B - 不同整数的最少数目 (opens new window)

class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int, int> cnt;
for (int i : arr)
cnt[i]++;
vector<int> c;
for (auto p : cnt)
c.emplace_back(p.second);
sort(c.begin(), c.end());
int t = c.size();
int sum = 0;
for (int i = 0; i < t; ++i) {
sum += c[i];
if (sum > k)
return t - i;
}
return 0;
}
};

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

## # Problem C - 制作 m 束花所需的最少天数 (opens new window)

typedef long long ll;

class Solution {
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if (n / k < m)
return -1;
int l = 1, r = 1e9;
auto check = [&](int x) {
vector<bool> flower(n);
for (int i = 0; i < n; ++i)
if (bloomDay[i] <= x)
flower[i] = true;
int bunch = 0, curr = 0;
for (int i = 0; i < n; ++i) {
if (flower[i])
curr++;
else {
bunch += curr / k;
curr = 0;
}
}
bunch += curr / k;
return bunch;
};
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid) < m)
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

## # Problem D - 树节点的第 K 个祖先 (opens new window)

class TreeAncestor {
vector<vector<int>> p;
public:
TreeAncestor(int n, vector<int>& parent) {
p = vector<vector<int>>(n, vector<int>(18, -1));
for (int i = 0; i < n; ++i)
p[i][0] = parent[i];
for (int k = 1; k < 18; ++k)
for (int i = 0; i < n; ++i) {
if (p[i][k - 1] == -1)
continue;
p[i][k] = p[p[i][k - 1]][k - 1];
}
}

int getKthAncestor(int node, int k) {
for (int i = 17; i >= 0; --i)
if (k & (1 << i)) {
node = p[node][i];
if (node == -1)
break;
}
return node;
}
};

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