# # Leetcode 第65场双周赛题解

## # Problem A - 检查两个字符串是否几乎相等 (opens new window)

### # 方法一：模拟

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

class Solution:
def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
cnt1 = collections.Counter(word1)
cnt2 = collections.Counter(word2)
return all(abs(cnt1[key] - cnt2[key]) <= 3 for key in set(cnt1.keys()) | set(cnt2.keys()))

1
2
3
4
5

## # Problem B - 模拟行走机器人 II (opens new window)

### # 方法一：优化模拟

• 初始化时间复杂度为$\mathcal{O}(W+H)$，其余操作时间复杂度为$\mathcal{O}(1)$
• 空间复杂度$\mathcal{O}(W+H)$

const string dirs[4] = {"East", "North", "West", "South"};

class Robot {
bool _moved;
int _pos, _n;
vector<int> _x, _y, _d;
public:
Robot(int width, int height) {
_moved = false;
_n = (width + height - 2) * 2;
_pos = 0;
_x = vector<int>(_n);
_y = vector<int>(_n);
_d = vector<int>(_n);

int x = 0, y = 0, i = 0;
_d[0] = 3;
for (int j = 1; j < width; ++j) {
x++, i++;
_x[i] = x, _y[i] = y, _d[i] = 0;
}
for (int j = 1; j < height; ++j) {
y++, i++;
_x[i] = x, _y[i] = y, _d[i] = 1;
}
for (int j = 1; j < width; ++j) {
i++, x--;
_x[i] = x, _y[i] = y, _d[i] = 2;
}
for (int j = 1; j < height - 1; ++j) {
i++, y--;
_x[i] = x, _y[i] = y, _d[i] = 3;
}
}

void move(int num) {
_moved = true;
_pos = (_pos + num) % _n;
}

vector<int> getPos() {
return {_x[_pos], _y[_pos]};
}

string getDir() {
if (!_moved)
return dirs[0];

return dirs[_d[_pos]];
}
};

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
49
50
51

## # Problem C - 每一个查询的最大美丽值 (opens new window)

### # 方法一：离线

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

class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
int n = items.size(), q = queries.size();
vector<int> ans(q);
vector<int> order(q);
for (int i = 0; i < q; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return queries[i] < queries[j];
});
sort(items.begin(), items.end());
int hi = 0, ptr = -1;
for (int i : order) {
while (ptr + 1 < n && items[ptr + 1][0] <= queries[i])
hi = max(hi, items[++ptr][1]);
ans[i] = hi;
}
return ans;
}
};

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

## # Problem D - 你可以安排的最多任务数目 (opens new window)

### # 方法一：二分答案+贪心

• 如果有人能完成当前任务，我们就安排其中能力值最小的那个人去做这一任务。
• 如果没有人能完成当前任务，但当前有药，并且有人能在服药后完成这一任务，我们就安排其中能力值最小的那个人去做这一任务。
• 否则说明无法完成$K$个任务。

• 如果当前有药，我们就安排服药后能够完成任务的人中能力值最小的那个人去做这一任务。但要注意这个人可能不吃药也能完成任务，此时就不必吃药了。~|
• 如果当前没有药，我们就安排能完成任务的人中能力值最小的那个人去做这一任务。
• 否则说明无法完成$K$个任务。

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

class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
int n = tasks.size(), m = workers.size();

sort(workers.begin(), workers.end());

auto check = [&](int k) {
if (m < k)
return false;

multiset<int> ms(workers.rbegin(), workers.rbegin() + k);
int rem = pills;
for (int i = k - 1; i >= 0; --i) {
// 贪心策略1
auto it = ms.lower_bound(tasks[i]);
if (it == ms.end()) {
if (rem == 0)
return false;
it = ms.lower_bound(tasks[i] - strength);
if (it == ms.end())
return false;
rem--;
ms.erase(it);
} else {
ms.erase(it);
}

// 贪心策略2（错误）
// if (rem) {
//     auto it = ms.lower_bound(tasks[i] - strength);
//     if (it == ms.end())
//         return false;
//     if (*it < tasks[i])
//         rem--;
//     ms.erase(it);
// } else {
//     auto it = ms.lower_bound(tasks[i]);
//     if (it == ms.end())
//         return false;
//     ms.erase(it);
// }
}

return true;
};

int lo = 1, hi = n;
while (lo <= hi) {
int mid = (lo + hi) >> 1;

if (check(mid))
lo = mid + 1;
else
hi = mid - 1;
}

return hi;
}
};

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
49
50
51
52
53
54
55
56
57
58
59
60
61

### # 方法二：单调队列

• 首先考虑这个工人不吃药的情况。此时我们看队列最前面，也即当前最容易的任务是否能够被完成。如果可以，则让该工人做这个最容易的任务。因为任务是必须要做的，而后面的人能力都比当前这个人要强，所以安排当前这个人来做任务是不亏的。
• 如果他不吃药就做不了任务，那就必须吃药。吃药之后，我们应该让他做当前最难的任务，也即队尾的任务。
• 如果吃了药也做不了任何任务，则说明无法完成$K$个任务。

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

class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
int n = tasks.size(), m = workers.size();

sort(workers.begin(), workers.end());

auto check = [&](int k) {
if (m < k)
return false;

int ptr = -1, rem = pills;
deque<int> dq;
for (int i = m - k; i < m; ++i) {
while (ptr + 1 < k && tasks[ptr + 1] <= workers[i] + strength)
if (dq.empty())
return false;
if (dq.front() <= workers[i])
dq.pop_front();
else if (rem > 0) {
rem--;
dq.pop_back();
} else
return false;
}

return true;
};

int lo = 1, hi = n;
while (lo <= hi) {
int mid = (lo + hi) >> 1;

if (check(mid))
lo = mid + 1;
else
hi = mid - 1;
}

return hi;
}
};

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