LeetCode biweekly contest 51

发表于 更新于 分类于 Disqus：
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种操作 Decrease 和 Rearrange 可以发现，
其实只需要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重新排序得到均摊速度更快的算法。

首先，将queries按minisize排序，将rooms按size排序。
用双指针的方式，保证对于当前的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).