leetcode weekly contest 308

竞赛手速场了，没啥好说的，都是常规题目。

6160. 和有限的最长子序列

题目

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中元素之和小于等于 queries[i] 的 子序列 的最大长度。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-308/problems/longest-subsequence-with-limited-sum/

题意

贪心算法

思路

题目太简单了，由于不需要子序列有序，就非常简单了，直接将数组 $nums$ 排序，长度为 $i$ 的子序列的最小和即为前 $i$ 项元素的和，我们依次贪心的尝试前 $i$ 项的和小于等于 $queries[i]$ 的最大 $i$ 即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(n \log n)$。

代码

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        int m = queries.size();
        vector<int> ans(m);
        vector<long long> minSum(n + 1);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            minSum[i+1] = minSum[i] + nums[i];
        }
        for (int i = 0; i < m; i++) {
           for(int j = n; j >= 0; j--) {
               if (minSum[j] <= queries[i]) {
                   ans[i] = j;
                   break;
               }
           }
        }
        return ans;
    }
};

6161. 从字符串中移除星号

题目

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

选中 s 中的一个星号。
移除星号左侧最近的那个 非星号 字符，并移除该星号自身。

返回移除所有星号之后的字符串。

注意：

生成的输入保证总是可以执行题面中描述的操作。
可以证明结果字符串是唯一的。

示例 1：

输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。

示例 2：

输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。

提示：

1 <= s.length <= 105
s 由小写英文字母和星号 * 组成
s 可以执行上述操作

地址

https://leetcode.cn/contest/weekly-contest-308/problems/removing-stars-from-a-string/

题意

栈

思路

跟左右括号匹配一个原理，无脑用栈求解即可，与到 * 从栈中弹出一个元素即可。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符串的长度。
空间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符串的长度。

代码

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

6162. 收集垃圾的最少总时间

题目

给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾一单位的任何一种垃圾都需要花费 1 分钟。

同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。

城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。

任何时刻只有一辆垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车不能做任何事情。

请你返回收拾完所有垃圾需要花费的最少总分钟数。

示例 1：

输入：garbage = ["G","P","GP","GG"], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。

示例 2：

输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

提示：

2 <= garbage.length <= 105
garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-308/problems/minimum-amount-of-time-to-collect-garbage/

题意

直接遍历

思路

题目出的非常奇怪，不知道想考什么，由于任何时间只有一辆车辆可以行动，所以根本不能在最优调动什么的，直接暴力计算每种垃圾车的运行的最短时间即可，稍微有点技巧的是需要注意到垃圾车不必走到最后一栋房子，只需要清理完最后一栋含有该垃圾的房子即可停止即可。

时间复杂度：时间复杂度为 $O(n)$，$n$ 为节点数目。
空间复杂度：空间复杂度为 $O(n)$，$n$ 为节点数目。

代码

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int n = garbage.size();
        vector<vector<int>> cnt(n, vector<int>(3));
        vector<int> last(3);
        for (int i = 0; i < n; i++) {
            for(auto c : garbage[i]) {
                if (c == 'M') {
                    cnt[i][0]++;
                } else if(c == 'P') {
                    cnt[i][1]++;
                } else if (c == 'G') {
                    cnt[i][2]++;
                }
            }
            for (int j = 0; j < 3; j++) {
                if (cnt[i][j] > 0) {
                    last[j] = i;
                }
            }
        }
        int tot = 0;
        vector<int> cost(3);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n && j <= last[i]; j++) {
                cost[i] += cnt[j][i];
                if (j > 0) {
                    cost[i] += travel[j - 1];
                }
            }
        }
        return cost[0] + cost[1] + cost[2];
    }
};

6163. 给定条件下构造矩阵

题目

给你一个正整数 k ，同时给你：

一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的行必须在数字 belowi 所在行的上面。
对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的列必须在数字 righti 所在列的左边。

返回满足上述要求的任意矩阵。如果不存在答案，返回一个空的矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
- 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
- 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 104
rowConditions[i].length == colConditions[i].length == 2
1 <= abovei, belowi, lefti, righti <= k
abovei != belowi
lefti != righti

地址

https://leetcode.cn/contest/weekly-contest-308/problems/build-a-matrix-with-conditions/

题意

拓扑排序

思路

简单的拓扑排序即可，首先我们观察一下行的顺序与列的顺序是互相分离的，互相不影响的，因此我们可以先计算出每个元素所处的行的位置，再计算出每个元素所处的列的位置解，这样即可得到元素 $1, 2 , \cdots, k$ 的行坐标与列坐标。
行或者列的依赖关系我们可以转换为有向图，如果行 $x$ 在行 $y$ 的上方，则有有向变从 $x$ 指向 $y$，此时只需要求出所有行或者列的先后顺序即可，此时我们很容易的用拓扑排序求出即可，此时我们即求出元素 $1, 2 , \cdots, k$ 的行或者列的顺序，最后将元素写会矩阵即可。需要注意的是如果拓扑排序失败，则表明依赖关系存在矛盾，直接返回空矩阵即可。
复杂度分析：

时间复杂度：$O(m + k^2)$，其中 $m$ 表示依赖关系数组的长度，$k$ 表示给定的 $k$。
空间复杂度：$O(k + m)$，其中 $m$ 表示依赖关系数组的长度，$k$ 表示给定的 $k$。

代码

class Solution {
public:
    vector<int> bfs(vector<vector<int>> &adj, vector<int> &degree, int k) {
        queue<int> qu;
        for(int i = 0; i < k; i++) {
            if (degree[i] == 0) {
                qu.emplace(i);
            }
        }
        vector<int> ret;
        while (!qu.empty()) {
            auto curr = qu.front();
            qu.pop();
            ret.emplace_back(curr);
            for (auto v : adj[curr]) {
                degree[v]--;
                if (degree[v] == 0) {
                    qu.emplace(v);
                }
            }
        }
        return ret;
    }
    
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> adjRow(k);
        vector<vector<int>> adjCol(k);
        vector<int> indegreeRow(k, 0);
        vector<int> indegreeCol(k, 0);
        for (auto v : rowConditions) {
            int x = v[0] - 1, y = v[1] - 1;
            adjRow[x].emplace_back(y);
            indegreeRow[y]++;
        }
        for (auto v : colConditions) {
            int x = v[0] - 1, y = v[1] - 1;
            adjCol[x].emplace_back(y);
            indegreeCol[y]++;
        }
        
        vector<int> rowIdx = bfs(adjRow, indegreeRow, k);
        vector<int> colIdx = bfs(adjCol, indegreeCol, k);
        if (rowIdx.size() < k || colIdx.size() < k) {
            return vector<vector<int>>();
        }
        vector<vector<int>> loc(k, vector<int>(2));
        for (int i = 0; i < k; i++) {
            loc[rowIdx[i]][0] = i;
            loc[colIdx[i]][1] = i;
        }
        vector<vector<int>> ans(k, vector<int>(k));
        for (int i = 0; i < k; i++) {
            int x = loc[i][0];
            int y = loc[i][1];
            ans[x][y] = i + 1;
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← AutoX 安途智行专场竞赛 leetcode weekly contest 307 →

扫描二维码，分享此文章