LeetCode biweekly contest 51

Rank Name Score Finish Time Q1 (3) Q2 (4) Q3 (5) Q4 (6)
150 / 9378 YoungForest 18 0:32:04 0:05:26 0:07:22 0:11:24 0:32:04

手速场。最近手速已大不如从前,最后一题也因为不熟练花费了比较多的时间。
其实,手速场中,所有题目的算法其实都不难,想到正确的解法很快,但迅速实现 + bug free就考验每位程序员的功力了。

1844. Replace All Digits with Characters

签到题。按照题目要求完成即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
char shift(char c, int x) {
return c + x;
}
public:
string replaceDigits(string s) {
for (int i = 1; i < s.size(); i += 2) {
s[i] = shift(s[i-1], s[i] - '0');
}
return s;
}
};

时间复杂度: O(N),
空间复杂度: O(1).

1845. Seat Reservation Manager

因为每次都找最小的座位号,同时有insert(unreserve)的操作。显然需要使用 priority_queue优先队列/Heap 实现这一需求。

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
class SeatManager {
priority_queue<int, vector<int>, greater<>> pq;
public:
SeatManager(int n) {
for (int i = 1; i <= n; ++i) {
pq.push(i);
}
}

int reserve() {
const int ans = pq.top();
pq.pop();
return ans;
}

void unreserve(int seatNumber) {
pq.push(seatNumber);
}
};

/**
* Your SeatManager object will be instantiated and called as such:
* SeatManager* obj = new SeatManager(n);
* int param_1 = obj->reserve();
* obj->unreserve(seatNumber);
*/

时间复杂度:

  • SeatManager: O(n),
  • reserve: O(log n),
  • unreserve: O(log n).
    空间复杂度: O(n).

1846. Maximum Element After Decreasing and Rearranging

贪心。
观察2种操作 DecreaseRearrange 可以发现,
其实只需要Reagrrage一次,Decrease时,优先减小的。因为大的减起来一定可以包括小的,但小的不行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
const int n = arr.size();
sort(arr.begin(), arr.end());
int last = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] > last) {
arr[i] = last + 1;
} else {
arr[i] = last;
}
last = arr[i];
}
return arr[n - 1];
}
};

时间复杂度: O(n log n + n),
空间复杂度: O(1).

1847. Closest Room

首先想到暴力解法,对于每一个query, 遍历一遍rooms,就可以找到答案。时间复杂度为 O(k * n),显然会TLE。
解法时间复杂度应该是类似O(n log n)这种形式。

这里需要用到一个所谓**离线计算(offline query)**的技术。
所谓在线计算,就是queries的解答顺序是不变的,类似一个函数,每次被call,解答一次。
所谓离线计算,就是queries的解答顺序是可以变的,需要一次性求解一个数组的queries。此时,我们可以通过对queries重新排序得到均摊速度更快的算法。

首先,将queriesminisize排序,将roomssize排序。
用双指针的方式,保证对于当前的query,符合要求的rooms都被加入候选集合中。这里我们用TreeSet维护候选集合,以实现log n的搜索最近room

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
class Solution {
public:
vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
// brute force: k * n
// need: k * log n + n log n
// online, sort queries by minisize from big to small, find close candidate
const int n = rooms.size();
sort(rooms.begin(), rooms.end(), [&](const auto& a, const auto& b) -> bool {
return a[1] > b[1];
});
const int k = queries.size();
using pii = pair<int, int>;
vector<pii> searchOrder; // miniSize, index
searchOrder.reserve(k);
for (int i = 0; i < k; ++i) {
searchOrder.push_back({queries[i][1], i});
}
sort(searchOrder.begin(), searchOrder.end(), [&](const auto& a, const auto& b) -> bool {
return a.first > b.first;
});
int i = 0;
set<int> candidate;
vector<int> ans(k, -1);
for (int j = 0; j < k; ++j) {
while (i < n && rooms[i][1] >= searchOrder[j].first) {
candidate.insert(rooms[i++][0]);
}
const int prefer = queries[searchOrder[j].second][0];
if (!candidate.empty()) {
auto it = candidate.lower_bound(prefer);
if (it == candidate.begin()) {
ans[searchOrder[j].second] = *it;
} else if (it == candidate.end()) {
ans[searchOrder[j].second] = *prev(it);
} else {
if (abs(*it - prefer) < (prefer - *prev(it))) {
ans[searchOrder[j].second] = *it;
} else {
ans[searchOrder[j].second] = *prev(it);
}
}
} else {
ans[searchOrder[j].second] = -1;
}
}
return ans;
}
};

时间复杂度: O(n log n + k log n + k log k),
空间复杂度: O(k + n).