Skip to content

第 327 场周赛

比赛链接

Date: 2023-01-08

A 正整数和负整数的最大计数

暴力

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int x = 0, y = 0;
        for (auto num : nums) {
            if (num < 0) x++;
            else if (num > 0) y++;
        }
        return max(x, y);
    }
};

1
2
3
4
5
6
7
8
9
class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        x, y = 0, 0
        for num in nums:
            if num < 0:
                x += 1
            elif num > 0:
                y += 1
        return max(x, y)

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)

B 执行 K 次操作后的最大分数

使用二叉堆维护当前最大值即可。上取整时使用 (x + (3 - 1)) / 3 即可实现上取整操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    using ll = long long;
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<ll> q;
        for (auto x : nums) q.push(x);
        ll res = 0;
        while (k--) {
            ll x = q.top();
            res += q.top(); q.pop();
            q.push((x + 2) / 3);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        h = sorted([-x for x in nums])
        res = 0
        for _ in range(k):
            x = heappop(h)
            res -= x
            heappush(h, -((-x + 2) // 3))
        return res

复杂度分析

  • 时间复杂度：\(O(k \log n)\)
  • 空间复杂度：\(O(n)\)

C 使字符串总不同字符的数目相等

使用哈希表记录每个字符出现的次数，由于每个字符串中的种类数不超过 26，所以可以用 26*26 的双层遍历来枚举替换情况。枚举时，有两种方法：

  • 构造哈希表的副本，然后修改后对比即可。这样写不容易写错。（C++ 实现）
  • 如果交换的是相同的字母，则跳过。否则根据交换的字母，根据实际的哈希表中的情况计算交换后的种类数进行对比。（容易写错，python 实现）
 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
class Solution {
public:
    bool isItPossible(string word1, string word2) {
        unordered_map<char, int> h1, h2;
        for (auto c : word1) h1[c]++;
        for (auto c : word2) h2[c]++;

        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                char x = 'a' + i;
                char y = 'a' + j;
                if (h1.count(x) && h2.count(y)) {
                    auto h1_c = h1, h2_c = h2;
                    h1_c[x]--; h1_c[y]++;
                    h2_c[y]--; h2_c[x]++;
                    int a = 0, b = 0;
                    for (auto &[k, v] : h1_c) if (v != 0) a++;
                    for (auto &[k, v] : h2_c) if (v != 0) b++;
                    if (a == b) return true;
                }
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        h1, h2 = Counter(word1), Counter(word2)
        l1, l2 = len(h1), len(h2)
        for x in h1:
            for y in h2:
                if x == y:
                    if l1 == l2:
                        return True
                    continue
                # 计算交换操作之后的种类数
                nl1 = l1 - 1 if h1[x] == 1 else l1
                nl2 = l2 - 1 if h2[y] == 1 else l2
                nl1 = nl1 + 1 if h1[y] == 0 else nl1
                nl2 = nl2 + 1 if h2[x] == 0 else nl2
                if nl1 == nl2:
                    return True
        return False

复杂度分析

  • 时间复杂度：\(O(C^4)\)，优化后的方法二为 \(O(C^2)\)
  • 空间复杂度：\(O(n)\)

D 过桥的时间

工人共有四种状态，每一种状态都存在优先级对比，大致可以分为两类：

  1. 在左右对岸等待的工人，优先级根据题目中给定进行计算
  2. 在搬起或者放下的工人，优先级根据完成时间来计算

因此，要设置四个优先队列来分别存储他们。当旧仓库还有货物或者右边还有人时，过程就需要继续：

  1. 首先，如果搬起或者放下的工人在此时已经完成，则将他们依次加入左边或者右边的等待队列。
  2. 然后，如果右边有人等待，则取优先级最低的工人过桥，过桥后放入左侧的处于「放下」状态的队列。
  3. 否则如果旧仓库还有货物，并且左侧有等待的工人，则取优先级最低的工人过桥，过桥后放入右侧处于「搬起」状态的队列，并使得旧仓库待搬运货物数量减一。
  4. 否则，此时没有人需要过桥，时间应该过渡到第一个处于「放下」或者「搬起」状态的工人切换状态的时刻。

按照上述过程模拟，直到结束即可。注意问题关注的是，最后一个回到左边的工人的到达时间，并不是最后放下货物的时间。

 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
class Solution {
public:
    using PII = pair<int, int>;
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        auto cmp = [&](int x, int y) {
            int l = (time[x][0] + time[x][2]);
            int r = (time[y][0] + time[y][2]);
            return l != r ? l < r : x < y;
        };

        // 左边和右边的等待队列
        priority_queue<int, vector<int>, decltype(cmp)> L(cmp), R(cmp);

        // 左边「放下」状态队列和右边「搬起」状态队列，PII 的第一关键字是完成时间，第二关键字是工人ID
        priority_queue<PII, vector<PII>, greater<PII>> ql, qr;

        // 剩余待处理货物数量和当前时间
        int rest = n, cur = 0;
        for (int i = 0; i < k; i++) L.push(i);

        while (rest > 0 || qr.size() > 0 || R.size() > 0) {
            // 1. 如果搬起或者放下的工人在此时已经完成，则将他们依次加入左边或者右边的等待队列。
            while (qr.size() && qr.top().first <= cur) {
                R.push(qr.top().second);
                qr.pop();
            }
            while (ql.size() && ql.top().first <= cur) {
                L.push(ql.top().second);
                ql.pop();
            }

            // 如果右边有人等待，则取优先级最低的工人过桥，过桥后放入左侧的处于「放下」状态的队列。
            if (R.size() > 0) {
                int x = R.top(); R.pop();
                cur += time[x][2];
                ql.push({cur + time[x][3], x});
            } else if (L.size() > 0 && rest > 0) {
            // 否则如果旧仓库还有货物，并且左侧有等待的工人，则取优先级最低的工人过桥，过桥后放入右侧处于「搬起」状态的队列，并使得旧仓库待搬运货物数量减一。
                int x = L.top(); L.pop();
                cur += time[x][0];
                qr.push({cur + time[x][1], x});
                rest--;
            } else {
            // 否则，此时没有人需要过桥，时间应该过渡到第一个处于「放下」或者「搬起」状态的工人切换状态的时刻。
                int x = 1e9;
                if (qr.size()) x = min(x, qr.top().first);
                if (ql.size()) x = min(x, ql.top().first);
                if (x != 1e9) cur = max(cur, x);
            }
        }
        return cur;
    }
};

复杂度分析

  • 时间复杂度：\(O(n\log k)\)
  • 空间复杂度：\(O(n)\)
本文访问 次