# # Leetcode 第226场周赛题解

## # Problem A - 盒子中小球的最大数量 (opens new window)

• 时间复杂度$\mathcal{O}((H-L)\log H)$
• 空间复杂度$\mathcal{O}(\log H)$

class Solution:
def countBalls(self, lowLimit: int, highLimit: int) -> int:
cnt = collections.Counter()
for i in range(lowLimit, highLimit + 1):
cnt[sum(map(int, list(str(i))))] += 1
return max(cnt.values())

1
2
3
4
5
6

## # Problem B - 从相邻元素对还原数组 (opens new window)

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

class Solution {
public:
unordered_map<int, int> in_deg;
for (auto &v : adjacentPairs) {
in_deg[v[0]]++;
in_deg[v[1]]++;
}
int start;
for (auto [num, deg] : in_deg) {
if (deg == 1) {
start = num;
break;
}
}
queue<int> q;
q.emplace(start);
vector<int> ans;
unordered_set<int> vis;
vis.emplace(start);
while (!q.empty()) {
int u = q.front();
q.pop();
ans.emplace_back(u);
for (int v : adj[u]) {
if (!vis.count(v)) {
vis.emplace(v);
q.emplace(v);
}
}
}
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
31
32
33
34
35
36
37

## # Problem C - 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ (opens new window)

• 每天按照上限$dailyCap_i$去吃，也无法把$favoriteType_i$之前的所有糖果吃完（包括刚好吃完的情形，因为我们还需要至少吃一个$favoriteType_i$类型的糖果）。
• 每天按照下限$1$去吃，也会在$favoriteDay_i$之前把$favoriteType_i$及之前的所有糖果吃完。

• 时间复杂度$\mathcal{O}(N+Q)$，其中$N$是糖果的种数，$Q$是询问的个数。
• 空间复杂度$\mathcal{O}(N)$

typedef long long ll;

class Solution {
public:
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int q = queries.size(), n = candiesCount.size();
vector<bool> ans(q);
vector<ll> pre(n + 1);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + candiesCount[i - 1];
for (int i = 0; i < q; ++i) {
int t = queries[i][0], d = queries[i][1], c = queries[i][2];
ll before = pre[t];

// Cannot eat type t even if we eat c candies every day.
if (1LL * c * (d + 1) <= before)
continue;

// Type t has been eaten out before day d.
if (d >= pre[t + 1])
continue;

ans[i] = true;
}
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

## # Problem D - 回文串分割 IV (opens new window)

• 用简单的中心扩展法以$\mathcal{O}(N^2)$的时间复杂度找出所有回文串。这里用Manacher可以将时间复杂度降到$\mathcal{O}(N)$，但并没有必要。

• 枚举第一段和第二段的结束位置，检查是否能分成三个回文串，同样是$\mathcal{O}(N^2)$的时间复杂度。

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

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

class Solution {
public:
bool checkPartitioning(string s) {
int n = s.size();
vector<vector<bool>> palin(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
int l = i, r = i;
while (l >= 0 && r < n && s[l] == s[r]) {
palin[l][r] = true;
l--;
r++;
}
l = i, r = i + 1;
while (l >= 0 && r < n && s[l] == s[r]) {
palin[l][r] = true;
l--;
r++;
}
}
for (int i = 0; i + 2 < n; ++i)
for (int j = i + 1; j + 1 < n; ++j) {
if (palin[0][i] && palin[i + 1][j] && palin[j + 1][n - 1])
return true;
}
return false;
}
};

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