赛中过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;
}
};