第 336 场周赛

比赛链接

Date: 2023-03-12

A 统计范围内的元音字符串数

class Solution {
public:
    bool ok(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
    int vowelStrings(vector<string>& words, int left, int right) {
        int res = 0;
        for (int i = left; i <= right; i++) {
            if (ok(words[i][0]) && ok(words[i].back())) {
                res++;
            }
        }
        return res;
    }
};

复杂度分析

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

B 重排数组以得到最大前缀分数

倒序排序计算前缀和即可。正数的顺序无所谓，负数一定要从大到小。

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        long long pre = 0, res = 0;
        for (auto x : nums) {
            pre += x;
            if (pre > 0) {
                res++;
            }
        }
        return res;
    }
};

复杂度分析

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

C 统计美丽子数组数目

如果一个子区间内所有数字的异或结果是 0，那么该子区间就是美丽的。因为同一位上每两个 1 配对，等同于 1 的个数相同，也就是说异或后为 0。

因此，用哈希来记录前缀中每种异或和的个数，对于每个位置的前缀异或和 mask，我们希望在前面找到同样是 mask 的个数，这样区间异或值就是 \(mask \oplus mask = 0\)。

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int mask = 0;
        long long res = 0;
        for (auto x : nums) {
            mask ^= x;
            res += mp[mask];
            mp[mask]++;
        }
        return res;
    }
};

复杂度分析

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

D 完成所有任务的最少时间

方法一

为了尽可能的使得多个任务同时运行（并发），我们应当尽可能的延迟任务的执行。

我们从小到大遍历所有时间 \([0, 2000]\), 每次将可以开始执行的任务加入到任务队列。一个任务 \([\textit{start}, \textit{end}, \textit{duration}]\)，表示这个任务可以有 \(\textit{idle} = \textit{end} - \textit{start} + 1 - \textit{duration}\) 是空闲的。我们将这个任务的 \(\{\textit{idle}, \textit{end}\}\) 加入到队列中。

每个时刻检查任务队列，如果其中某个任务的 \(\textit{idle}\) 小于等于 \(0\)，则表示当前时刻必须执行任务。如果这个条件不满足，那么此刻就不执行任务，将队列中所有任务的 \({idle}\) 减去 \(1\)。

任务会有完成的时刻，如果某个任务的 \(\textit{end}\) 小于等于当前时刻，则剔除该任务。

class Solution {
public:
    using PII = pair<int, int>;
    int findMinimumTime(vector<vector<int>>& tasks) {
        vector<PII> q;
        int res = 0;
        sort(tasks.begin(), tasks.end());
        for (int t = 1, i = 0; t <= 2000; t++) {
            // 将可以开始执行的任务加入队列
            while (i < tasks.size() && tasks[i][0] == t) {
                q.push_back({tasks[i][1] - tasks[i][0] + 1 - tasks[i][2], tasks[i][1]});
                i++;
            }

            // 如果某些任务的 idle_time 小于等于 0，则当前时刻必须执行任务
            bool fg = false;
            for (auto &&[idle_time, end_time] : q) {
                if (idle_time <= 0) {
                    fg = true;
                }
            }
            if (fg) {
                res++;
            } else {
                // 如果当前时刻不执行，则所有任务 idle_time - 1
                for (auto &&[idle_time, end_time] : q) {
                    idle_time--;
                }
            }

            // 如果有些任务已经执行完成，则剔除队列
            for (int k = int(q.size()) - 1; k >= 0; k--) {
                if (q[k].second <= t) {
                    q.erase(q.begin() + k);
                }
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：\(O(Tn)\)，其中 \(T\) 是总时间，\(n\) 是任务数量。
• 空间复杂度：\(O(n)\)。

方法二

用优先队列替换掉普通的队列，但是原生的优先队列并不能方便的将所有任务 \(\textit{idle}\) 减去 \(1\)。因此，我们维护一个外部变量 \(\textit{offset}\)，表示我们总共减去多少次。那么有新的任务加入时，需要将它的 \(\textit{idle}\) 加上 \(\textit{offset}\) 来弥补。

class Solution {
public:
    using PII = pair<int, int>;
    int findMinimumTime(vector<vector<int>>& tasks) {
        int res = 0, offset = 0;
        sort(tasks.begin(), tasks.end());
        priority_queue<PII, vector<PII>, greater<PII>> q;
        for (int t = 1, i = 0; t <= 2000; t++) {
            // 将可以开始执行的任务加入队列
            while (i < tasks.size() && tasks[i][0] == t) {
                q.push({tasks[i][1] - tasks[i][0] + 1 - tasks[i][2] + offset, tasks[i][1]});
                i++;
            }

            // 如果某些任务的 idle_time 小于等于 0，则当前时刻必须执行任务
            if (q.size() && q.top().first - offset <= 0) {
                res++;
            } else {
                // 如果当前时刻不执行，则所有任务 idle_time - 1
                offset++;
            }

            // 如果有些任务已经执行完成，则剔除队列
            while (q.size() && q.top().second <= t) {
                q.pop();
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：\(O(T\log n)\)，其中 \(T\) 是总时间，\(n\) 是任务数量。
• 空间复杂度：\(O(n)\)。

方法三

现在还有一个瓶颈是时间，如果时间扩大到无法枚举的范围时，以上解法将超时。因此，我们需要将时间分段处理，来批量的控制每个任务的闲时时间。

class Solution {
public:
    using PII = pair<int, int>;
    int findMinimumTime(vector<vector<int>>& tasks) {
        // 将所有可能涉及到的时间加入到 times 中
        vector<int> times;
        for (auto &t : tasks) {
            times.push_back(t[0] - 1);
            times.push_back(t[1]);
        }
        sort(times.begin(), times.end());
        times.resize(unique(times.begin(), times.end()) - times.begin());

        int res = 0, offset = 0;
        sort(tasks.begin(), tasks.end());
        priority_queue<PII, vector<PII>, greater<PII>> q;
        for (int i = 1, j = 0; i < times.size(); i++) {
            int segTime = times[i] - times[i - 1];
            while (j < tasks.size() && tasks[j][0] <= times[i]) {
                q.push({tasks[j][1] - tasks[j][0] + 1 - tasks[j][2] + offset, tasks[j][1]});
                j++;
            }

            // 如果某些任务的空闲时间不够覆盖当前 segTime，则这些任务必须执行
            if (q.size() && q.top().first - offset <= segTime) {
                int execTime = segTime - (q.top().first - offset);
                res += execTime;
                offset += segTime - execTime;
            } else {
                offset += segTime;
            }

            while (q.size() && q.top().second <= times[i]) {
                q.pop();
            }
        }

        return res;
    }
};

复杂度分析

• 时间复杂度：\(O(n\log n)\)，\(n\) 是任务数量。
• 空间复杂度：\(O(n)\)。

本文访问 次