# # Leetcode 第243场周赛题解

## # Problem A - 检查某单词是否等于两单词之和 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(|S_1|+|S_2|+|S_3|)$
• 空间复杂度$\mathcal{O}(1)$

def to_int(s):
return int(''.join(map(lambda x: str(ord(x) - ord('a')), s)))

class Solution:
def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:

1
2
3
4
5
6

## # Problem B - 插入后的最大值 (opens new window)

### # 方法一：贪心

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

class Solution:
def maxValue(self, n: str, x: int) -> str:
if n[0] == '-':
for i in range(1, len(n)):
if int(n[i]) > x:
return n[:i] + str(x) + n[i:]
return n + str(x)
else:
for i in range(len(n)):
if int(n[i]) < x:
return n[:i] + str(x) + n[i:]
return n + str(x)


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

## # Problem C - 使用服务器处理任务 (opens new window)

### # 方法一：优先队列模拟

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

using ll = long long;

class Solution {
public:
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq, pq2;
int n = servers.size();
for (int i = 0; i < n; ++i)
pq2.emplace(servers[i], i);

int now = 0;
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
now = max(now, i);
while (!pq.empty() && pq.top().first <= now) {
pq2.emplace(servers[pq.top().second], pq.top().second);
pq.pop();
}
if (pq2.empty()) {
int t = pq.top().first;
while (!pq.empty() && pq.top().first == t) {
pq2.emplace(servers[pq.top().second], pq.top().second);
pq.pop();
}
now = t;
}
auto[w, idx] = pq2.top();
pq2.pop();
ans[i] = idx;
}

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

## # Problem D - 准时抵达会议现场的最小跳过休息次数 (opens new window)

### # 方法一：动态规划

$f[i]$表示跳过$i$次时的最短时间，则对于每一段路程，我们可以选择跳过（$i\rightarrow i+1$）或不跳过$(i\rightarrow i)$，分别进行转移。

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

class Solution {
public:
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
int n = dist.size();
int sum = 0;
for (int di : dist)
sum += di;
if (1LL * speed * hoursBefore < sum)
return -1;

auto inf = make_pair(INT_MAX, INT_MAX);
vector<pair<int, int>> f(n + 1, inf);
f[0] = make_pair(0, 0);
for (int di : dist) {
vector<pair<int, int>> nf(n + 1, inf);
for (int i = 0; i <= n; ++i) {
if (f[i] < inf) {
auto [t, d] = f[i];
nf[i] = min(nf[i], make_pair(t + (d + di - 1) / speed + 1, 0));
if (i + 1 <= n)
nf[i + 1] = min(nf[i + 1], make_pair(t + (d + di) / speed, (d + di) % speed));
}
}
f = move(nf);
}
auto target = make_pair(hoursBefore, 0);
for (int i = 0; i <= n; ++i)
if (f[i] <= target)
return i;

return -1;
}
};

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