第 308 场周赛

比赛链接

A 和有限的最长子序列

对 \(nums\) 从小到大排序，对于每个 \(query\)，优先考虑较小的元素即可，直到不能再继续扩充。注意题目中子序列的定义是不连续的，这意味着顺序可以打乱。由于 \(n, m \le 1000\)，所以直接暴力即可，时间复杂度为 \(O(n\log n+ nm)\)。

Note

本题也可以将 \(nums\) 排序后求前缀和 \(sum\) ，然后对于每个询问二分找最大的 \(idx\) 使得 \(sum[idx] \le querys[i]\)。时间复杂度为 \(O(n\log n + m \log n)\) 。

C++Python

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& q) {
        sort(nums.begin(), nums.end());
        int m = q.size();
        vector<int> res(m);
        for(int i= 0; i < m; i++) {
            int sum = q[i];
            int cnt = 0;
            while(cnt < nums.size() && sum >= nums[cnt]) {
                sum -= nums[cnt];
                cnt ++;
            }
            res[i] = cnt;
        }
        return res;
    }
};

class Solution:
    def answerQueries(self, nums: List[int], q: List[int]) -> List[int]:
        nums.sort()
        n = len(q)
        res = [0] * n
        for i in range(n):
            j = 0
            while j < len(nums) and q[i] >= nums[j]:
                q[i] -= nums[j]
                j += 1
            res[i] = j
        return res

B 从字符串中移除星号

本题中保证了输入总是可以执行题面中的操作，意味着每一个 * 的左侧一定可以找到一个唯一的非 * 字符与之配对。所以，这个过程类似于括号匹配，用栈去处理即可。

维护一个栈，从左到右遍历每个字符，遇到非 * 就加入栈，遇到 * 就弹出栈顶元素。最后栈底到栈顶就是答案。

在 C++ 中，本题的栈可以直接用 string 来实现。

C++Python

class Solution {
public:
    string removeStars(string s) {
        string t = "";
        for(auto &c : s) {
            if(c == '*') {
                t.pop_back(); 
            } else {
                t.push_back(c);
            }
        }
        return t;
    }
};

    class Solution:
    def removeStars(self, s: str) -> str:
        t = []
        for ch in s:
            if ch == '*':
                t.pop()
            else:
                t.append(ch)
        return ''.join(t)

C 收集垃圾的最少总时间

每种垃圾之间互不干扰，是互相独立的。而答案是单独处理每种垃圾的时间总和。

我们先处理 M 垃圾，从左往右遍历时，设 last 表示垃圾车上一次处理该垃圾所处的房子编号。只有当前遍历的房子含有 M 号垃圾时，才从 last 走到 i。因此，我们还需要维护这一步走过的距离之和 sum，每次遇到新的 i: 1. 将答案增加 sum 2. 将答案增加 count(garbage[i], 'M') 3. sum = 0 3. if(i + 1 < n) sum = travel[i]

对于 P 和 G，做同样处理。

C++Python

class Solution {
public:
    int garbageCollection(vector<string>& g, vector<int>& t) {
        int n = g.size();
        int sum = 0;
        auto get = [&](char ch) {
            int sum = 0, res = 0;
            for(int i = 0; i < n; i++) {
                if(g[i].find(ch) != string::npos) {
                    res += sum + count_if(g[i].begin(), g[i].end(), [ch](const char& c) { return c == ch; });
                    sum = 0;
                }
                if(i + 1 < n) sum += t[i];
            }
            return res;
        };
        sum += get('M') + get('P') + get('G');
        return sum;
    }
};

class Solution:
    def garbageCollection(self, garbage: List[str], t: List[int]) -> int:
        n, res = len(garbage), 0
        def get(ch):
            res, s = 0, 0
            for i in range(n):
                if ch in garbage[i]:
                    res += s + garbage[i].count(ch)
                    s = 0
                if i + 1 < n:
                    s += t[i]
            return res
        for ch in {'M', 'P', 'G'}:
            res += get(ch)
        return res

D 给定条件下构造矩阵

拓扑排序模版题，谁必须出现在谁之前，构建有向图，然后可知在行和列两个方向上各个元素之间可行的相对关系。按照这个顺序去填即可。

设 \(m\) 为行和列上约束的个数，那么时间复杂度就是 \(O(m)\)。

CPPPython

    class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        auto get = [&](vector<vector<int>> &g) {
            vector<vector<int>> e(k);   // 邻接表
            vector<int> deg(k);         // 度数表
            queue<int> q;               // 队列
            for(auto &v : g) {
                e[v[0] - 1].push_back(v[1] - 1); // 点编号整体减去一，方便处理
                deg[v[1] - 1] ++;
            }

            vector<int> res;
            for(int i = 0; i < k; i++) {
                if(deg[i] == 0) q.push(i);  // 拓扑排序，入度为 0 的点入队
            }
            while(q.size()) {
                int x = q.front(); q.pop();
                res.push_back(x);
                for(auto &y : e[x]) {
                    if(--deg[y] == 0)
                        q.push(y);
                }
            }
            return res;
        };

        auto row = get(rowConditions);
        auto col = get(colConditions);

        // 如果约束关系中有环存在，那么拓扑序的长度将比 k 小，此情况无解
        if(row.size() != k || col.size() != k) return vector<vector<int>>();

        vector<vector<int>> res(k, vector<int>(k));
        vector<pair<int, int>> pos(k); // 每个元素的横坐标和纵坐标
        for(int i = 0; i < k; i++) {
            pos[row[i]].first = i;
        }
        for(int i = 0; i < k; i++) {
            pos[col[i]].second = i;
        }
        for(int i = 0; i < k; i++) {
            res[pos[i].first][pos[i].second] = i + 1;
        }
        return res;
    }
};

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo(g):
            e = defaultdict(list)
            deg = [0] * k
            for u, v in g:
                u -= 1
                v -= 1
                e[u].append(v)
                deg[v] += 1

            res = []
            q = deque([i for i in range(k) if deg[i] == 0])
            while q:
                x = q.popleft()
                res.append(x)
                for y in e[x]:
                    deg[y] -= 1
                    if deg[y] == 0:
                        q.append(y)
            return res

        row, col = topo(rowConditions), topo(colConditions)
        if len(row) != k or len(col) != k:
            return []
        mpx = {idx : x for x, idx in enumerate(row)}
        mpy = {idx : y for y, idx in enumerate(col)}
        res = [[0] * k for _ in range(k)]
        for x in range(k):
            res[mpx[x]][mpy[x]] = x + 1
        return res

本文访问 次