相关信息：
- 第 308 场周赛题目列表：
- 完成程度：√√√×。
- 心得：
- 前三题比较简单，第四题做了半天居然想不起来要用拓扑排序，没做出来。
题目 1：和有限的最长子序列
核心思路：
- 该题理解题意后比较简单。
- 其实就是对于
queries[i]，使得 nums 中尽量多的元素求和小于等于 queries[i]。 - 因此直接贪心 + 排序 + 前缀和 + 二分即可。
- 即排序后计算前缀和数组，接着二分找到求和数组中低于
queries[i] 的位置即可。
代码实现：
class Solution
{
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries)
{
int n = nums.size(), m = queries.size();
sort(nums.begin(), nums.end());
for(int i = 1; i < n; ++i) nums[i] += nums[i-1];
vector<int> ans(m);
for(int i = 0; i < m; ++i)
ans[i] = upper_bound(nums.begin(), nums.end(), queries[i]) - nums.begin();
return ans;
}
};
题目 2：从字符串中移除星号
核心思路：
- 该题几乎就是送分题，比第一题还要简单些。
- 从前往后模拟的话需要维护栈，从后往前模拟更为简单。
代码实现：
class Solution
{
public:
string removeStars(string s)
{
string ans;
int cnt = 0;
for(int i = s.size()-1; i >= 0; --i)
{
if(s[i] == '*') ++cnt;
else if(cnt == 0) ans += s[i];
else --cnt;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
题目 3：收集垃圾的最少总时间
核心思路：
- 该题几乎也是送分题。
- 题目很长，但其实就是贪心解题。
- 计算每一个垃圾的总处理时间，其实就是计算每一个字符串的长度总和。
- 接着计算每个垃圾车移动的最远距离。【此处用前缀和即可】
代码实现：
class Solution
{
public:
int garbageCollection(vector<string>& garbage, vector<int>& travel)
{
int cnt = 0;
for(int i = 1; i < travel.size(); ++i) travel[i] += travel[i-1];
int a = 0, b = 0, c = 0;
for(int i = 0; i < garbage.size(); ++i)
{
string& tmp = garbage[i];
cnt += tmp.size();
if(tmp.find('M') != tmp.npos) a = i;
if(tmp.find('P') != tmp.npos) b = i;
if(tmp.find('G') != tmp.npos) c = i;
}
if(a != 0) cnt += travel[a-1];
if(b != 0) cnt += travel[b-1];
if(c != 0) cnt += travel[c-1];
return cnt;
}
};
题目 4：给定条件下构造矩阵
核心思路：
- 该题其实就是拓扑排序之后重构每个数字所在的行和列，做了半个小时愣是没想起来要用拓扑排序。
- 行和列的处理是一样的，先理解如何处理行即可。
- 对于
rowConditions[i] = [above_i, below_i]，可以认为 above_i 向 below_i 连一条有向边，因此根据其构成的有向图，可以进行拓扑排序，得到的拓扑序就是行中数字的相对顺序。 - 再根据拓扑序构造矩阵即可。
- 一开始也想明白要找到相对顺序，但莫名其妙用并查集开始做了，只能说太不熟练，需要多练，该题其实难度不大，只考察了一点拓扑排序。
代码实现：
class Solution
{
private:
vector<int> topoSort(vector<vector<int>>& edges, int k)
{
vector<vector<int>> graph(k+1);
vector<int> in(k+1);
for(int i = 0; i < edges.size(); ++i)
++in[edges[i][1]], graph[edges[i][0]].push_back(edges[i][1]);
vector<int> ans;
stack<int> stk;
for(int i = 1; i <= k; ++i) if(in[i] == 0)
stk.push(i);
while(!stk.empty())
{
int x = stk.top();
stk.pop();
ans.push_back(x);
for(auto& next : graph[x]) if(--in[next] == 0)
stk.push(next);
}
return ans;
}
public:
vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rc, vector<vector<int>>& cc)
{
auto row = topoSort(rc, k), col = topoSort(cc, k);
if(row.size() < k or col.size() < k) return {};
vector<int> pos(k);
for(int i = 0; i < k; ++i) pos[col[i]-1] = i;
vector<vector<int>> ans(k, vector<int>(k));
for(int i = 0; i < k; ++i)
ans[i][pos[row[i]-1]] = row[i];
return ans;
}
};
|