【力扣周赛308 场】拓扑排序

赛中过3题...最后一题应该是拓扑排序，但是我当时是往这方面想的，但是用的是dfs不知道为什么错...
比赛链接

T1.和有限的最长子序列

题意：给一个长度为n的序列，以及q次询问x，返回序列中满足和小于等于x的最大子序列长度

思路：子序列不要求连续，就是选或不选的概念，直接sort一遍进行二分即可。
我还是不习惯0下标的前缀和。

代码：

class Solution {
public:
    int a[1100];
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        for (int i=0;i<n;i++)
            a[i+1] = nums[i];
        sort(a+1,a+1+n);
        for (int i=1;i<=n;i++)
            a[i]+=a[i-1];
        vector<int> res;
        for (auto e:queries)
        {
            int x = upper_bound(a+1,a+1+n,e)-a-1;
            res.push_back(x);
        }
        return res;
    }
};

T2.从字符串中移除星号

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

在一步操作中，你可以：

选中 s 中的一个星号。
移除星号 左侧最近的那个 非星号 字符，并移除该星号自身。
返回移除所有星号之后的字符串。

思路：因为是要删除星号左边的，所以我倒着来看，如果遇到星号就cnt++，如果不是就看有没有cnt，如果有的话表示一定要删掉的，因为你当前这个字符会被右边的删除，没有的话则可以输出。

用一个标记数组vis就好

代码：

class Solution {
public:
    bool vis[100007];
    string removeStars(string s) {
        int n = s.size(), cnt = 0;
        string res;
        for (int i=n-1;i>=0;i--)
        {
            if (s[i]=='*') {cnt++;continue;}
            if (cnt) cnt--, vis[i] = true;
        }
        for (int i=0;i<n;i++)
        {
            if (s[i]=='*'||vis[i]) continue;
            res += s[i];
        }
        return res;
    }
};

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

题意：有三垃圾车要去若干站，每一站要求的垃圾车是不一样的，然后只能单线程进行，问最小时间。

思路：模拟没什么好说的...

代码：

class Solution {
public:
    int pos[26];
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int res = 0, n = garbage.size(), m = travel.size();
        for (int i=0;i<garbage.size();i++)
        {
            auto s = garbage[i];
            for (auto c:s)
            {
                int x = c-'A';
                for (int j=pos[x];j<i;j++)
                    res += travel[j];
                pos[x] = i;
                res += 1;
            }
        }
        return res;
    }
};

T4.给定条件下构造矩阵（拓扑排序）

题意：给你一个正整数n，以及两个数组rowConditions,colConditions，数组里面各包含两个数。

rowConditions[i]有两个数[x,y]表示x要在y的上边。
colConditions[i]有两个数[x,y]表示x要在y的左边。

问是否能够构造出一个k x k矩阵，其他数字填0即可。

思路：
我们对于每个[x,y]建边，表示y的优先级要比x高，我之前想的是深度，然后k个数里面深度为0的肯定先排下面，然后再排深度为1的...
可以看出，这个就是拓扑排序出栈顺序，先出栈的代表没有入边了，所以代表这个点能放了。

代码：

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rc, vector<vector<int>>& cc) {
        int n = rc.size(), m = cc.size();
        vector<vector<int>> res(k, vector<int>(k));
        vector<vector<int>> Null;
        vector<vector<int>> e(k+1);
        vector<int> r(k+1),c(k+1);
        vector<int> in(k+1);
        for (auto p:rc)
        {
            int x = p[0], y = p[1];
            e[y].push_back(x);
            in[x]++;
        }
        queue<int> q;
        for (int i=1;i<=k;i++)
            if (in[i]==0) q.push(i);
        int cnt = k;
        while (!q.empty())
        {
            int x = q.front();q.pop();
            cnt--;
            r[x] = cnt;
            for (auto y:e[x])
            {
                in[y]--;
                if (in[y]==0) q.push(y);
            }
        }
        if (cnt) return Null;
        cnt = k;
        for (int i=1;i<=k;i++) in[i] = 0,e[i].clear();
        for (auto p:cc)
        {
            int x = p[0], y = p[1];
            e[y].push_back(x);
            in[x]++;
        }
        for (int i=1;i<=k;i++)
            if (in[i]==0) q.push(i);
        while (!q.empty())
        {
            int x = q.front();q.pop();
            cnt--;
            c[x] = cnt;
            for (auto y:e[x])
            {
                in[y]--;
                if (in[y]==0) q.push(y);
            }
        }
        if (cnt) return Null;
        for (int i=1;i<=k;i++)
            res[r[i]][c[i]] = i;
        return res;
    }
};