308场周赛 leetcode xp_xht123

每周的周赛，虽然不能每一次ak，但是肯定还是需要总结的，从308场周赛开始总结

第一题，2389，和有限的最长子序列

题目描述：

给你一个长度为 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 。

前缀和+排序

首先先排序，然后计算前缀和，最后对于每一个询问，到序遍历一遍数组即可，即可找到答案，这样的复杂度为，当然可以使用二分查找去找到合适的坐标，这样时间复杂度可以降到

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) 
    {
        vector<int>res;
        sort(nums.begin() , nums.end());
        int s[1010];
        s[0] = nums[0];
        for(int i = 1;i < nums.size();i ++)
            s[i] = s[i - 1] + nums[i];
        
        for(int i = 0;i < queries.size();i ++)
        {
            int x = queries[i];
            
            if(x < s[0])
            {
                res.push_back(0);
                continue;
            }
            int j;
            for(j = nums.size() - 1;j >= 0;j --)
            {
                if(s[j] <= x) break;
            }
            
            res.push_back(j + 1);
        }
        return res;
    }
};

第二题：2309从字符串中移除星号

题目描述：

给你一个包含若干星号 * 的字符串 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*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。

栈的应用

首先先建立一个栈，每次遇见一个不是星号的字符推入栈，如果是星号，在保证栈非空的情况下弹出栈顶，最后栈中的元素逆序就是答案

class Solution {
public:
    string removeStars(string s) 
    {
        stack<char>st;
        
        for(int i = 0;i < s.length();i ++)
        {
            if(s[i] != '*') st.push(s[i]);
            else 
            {
                if(!st.empty()) st.pop();
            }
        }
        string res;
        
        while(!st.empty())
        {
            char ch = st.top();
            st.pop();
            res += ch;
        }
        
        if(res.size()) reverse(res.begin() , res.end());
        return res;
    }
};

第三题：

题目描述

给你一个下标从 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 分钟收拾完所有的垃圾。

前缀和+模拟

先计算，时间的前缀和，每一种情况，只用找到到达最远的位置所需要的时间+处理每一种情况所用的处理时间数就行，把所有的情况算出即可求出答案

class Solution 
{
public:
    int s[100010] = {0};
    unordered_map<int , vector<int> >mp;
public:
 
    void get_time(int type , int &res , int n)
    {
        int idx = 0;
        for(int j = 0;j < n;j ++)
        {
            if(mp[j][type])
            {
                res += mp[j][type];
                idx = j;
            }
        }
        if(idx >= 1) res += s[idx - 1];
    }
 
    int garbageCollection(vector& garbage, vector<int>& travel) 
    {
        s[0] = travel[0];
        for(int i = 1;i < travel.size();i ++)
            s[i] = s[i - 1] + travel[i];
        
        int n = garbage.size();
        for(int i = 0;i < n;i ++)
        {
            string x = garbage[i];
            int m = 0 , p = 0 , g = 0;
            
            for(int j = 0;j < x.size();j ++)
            {
                if(x[j] == 'M') m ++;
                else if(x[j] == 'P') p ++;
                else g ++;
            }
            mp[i].push_back(m) , mp[i].push_back(p) , mp[i].push_back(g);
        }
        
        int res = 0;
        for(int i = 0;i < 3;i ++)
            get_time(i , res , n);
        return res;
    }
};

第四题：

题目描述：

给你一个 正 整数 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 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

拓扑排序

当时一开始做的时候想到的是dfs，一直做不出来，结束了看了解析豁然开朗，原来是拓扑排序，分别对行和列进行拓扑排序，求出每个数字所在的排名。如果拓扑排序不存在，则说明答案不存在。按照行和列的排名填充最终的矩阵。

class Solution {
public:
 
    vector<int> tops(int k , vectorint>>& v)
    {
        vector<int>res(k);
        int d[410] = {0};
        vectorint>>g(k);
 
        //拓扑排序做事的顺序
 
        for(auto i : v)
        {
            int a = i[0] - 1 , b = i[1] - 1;
            g[a].push_back(b);
            d[b] ++;
        }
 
        queue<int>q;
        //找起点 入度为0的点
        for(int i = 0;i < k;i ++)
            if(!d[i]) q.push(i);
 
        int x = 0;
        while(!q.empty())
        {
            int t = q.front();
            q.pop();
 
            res[t] = x ++;
 
            for(int i : g[t])
            {
                d[i] --;
                if(!d[i]) q.push(i);
            }
        }
 
        for(int i = 0;i < k;i ++)
            if(d[i]) return {};
 
        return res;
    }
 
 
    vectorint>> buildMatrix(int k, vectorint>>& rowConditions, vectorint>>& colConditions) 
    {
        vector<int>r = tops(k , rowConditions);
        if(r.empty()) return {};
 
        auto c = tops(k , colConditions);
        if(c.empty()) return {};
 
        vectorint> >res(k, vector<int>(k , 0));//定义一个k * k的矩阵每个位置都为0
 
        for(int i = 0;i < k;i ++)
            res[r[i]][c[i]] = i + 1; 
 
        return res;
    }
};