前言:很久没做周赛了,上次做周赛还是本科期间(两年前),因为过几个月就要找实习了,所以最近开始打周赛,希望能继续加油。
这题的关键是读懂子序列的含义:
子序列 是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。
所以这个子序列可以是整个序列中任意的一部分,这一部分可以是不连续的一部分。所以我们要找出最长的子序列,只需要找到最小的N个子序列。这其实是一种贪心方法,我们排序后,求出当前和数组nums_sum。然后确定当前query比nums_sum[i]小的下标,添加到ans当中。
- class Solution {
- public:
- vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
- vector<int> ans;
- // 排序后找最小序列和
- sort(nums.begin(), nums.end());
- int nums_sum[nums.size()];
- nums_sum[0] = nums[0];
- for (int i = 1; i < nums.size(); i++) {
- nums_sum[i] = (nums[i] + nums_sum[i - 1]);
- }
- for (int i = 0; i < queries.size(); i ++) {
- if (queries[i] < nums_sum[0]) {
- ans.push_back(0);
- if (queries.size() == 1) {
- return ans;
- }
- // continue;
- } else if (queries[i] >= nums_sum[nums.size() - 1]) {
- ans.push_back(nums.size());
- // continue;
- } else {
- for (int j = 0; j < nums.size(); j++) {
- if (queries[i] < nums_sum[j]) {
- ans.push_back(j);
- break;
- }
- }
- }
- }
- return ans;
- }
- };
这题就是一个非常简单的字符串操作。所有涉及字符串删除的操作,新建一个比在原字符串上删除操作更方便!
- class Solution {
- public:
- string removeStars(string s) {
- string ans = "";
- if (s.empty()) {
- return ans;
- }
- for (int i = 0; i < s.size(); i++) {
- if (s[i] == '*') {
- ans.pop_back();
- } else {
- ans.push_back(s[i]);
- }
- }
- return ans;
- }
- };
分三步:
1、先找到每种垃圾最后一次出现的index,此时每次出现M、P、G都在ans上直接加1.
2、根据最后一次出现的index,计算计算travel。
3、将表示M、P、G的ans[0]、ans[1]、ans[2]相加返回答案。
- class Solution {
- public:
- int garbageCollection(vector<string>& garbage, vector<int>& travel) {
- int ans[3]; // m p g
- for (int i = 0; i < 3; i++) {
- ans[i] = 0;
- }
- // 先找到每种垃圾最后一次出现的index
- int index[3]; // m p g
- for (int i = 0; i < 3; i++) {
- index[i] = -1;
- }
- for (int i = 0; i < garbage.size(); i++) {
- for (int j = 0;j < garbage[i].size(); j++) {
- if (garbage[i][j] == 'M') {
- index[0] = i;
- ans[0] ++;
- } else if (garbage[i][j] == 'P') {
- index[1] = i;
- ans[1] ++;
- } else if (garbage[i][j] == 'G') {
- index[2] = i;
- ans[2] ++;
- }
- }
- }
- // 计算travel
- for (int i = 0; i < 3; i++) {
- if (index[i] == -1) {
- continue;
- }
- for (int j = 0; j < index[i]; j++) {
- ans[i] += travel[j];
- }
- }
- return ans[0] + ans[1] + ans[2];
-
-
- // for (int i = 0; i < garbage.size(); i++) {
- // for (int j = 0; j < garbage[i].size(); j++) {
- // // M
- // if (flagm == true && i > 0) {
- // ansm += travel[i - 1];
- // }
- // if (garbage[i][j] == 'M') {
- // ansm ++;
- // flagm = true;
- // }
- // // P
- // if (flagp == true && i > 0) {
- // ansm += travel[i - 1];
- // }
- // if (garbage[i][j] == 'P') {
- // ansp ++;
- // flagp = true;
- // }
- // // G
- // if (flagg == true && i > 0) {
- // ansm += travel[i - 1];
- // }
- // if (garbage[i][j] == 'G') {
- // ansg ++;
- // flagg = true;
- // }
- // }
- // }
-
- // return ansm+ansp+ansg;
- }
- };
没时间写了,很久没打比赛手速很慢,贴一个大佬的答案,下周继续加油吧~
分别对行列的条件约束进行两次拓扑排序:
- class Solution:
- def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
- def topo(edges):
- web = [[] for _ in range(k + 1)]
- ind = [0] * (k + 1)
-
- for u, v in edges:
- web[u].append(v)
- ind[v] += 1
-
- q = [u for u in range(1, k + 1) if not ind[u]]
- head, tail = 0, len(q)
- while head < tail:
- u = q[head]
- head += 1
- for v in web[u]:
- ind[v] -= 1
- if not ind[v]:
- q.append(v)
- tail += 1
-
- return q if tail == k else []
-
- A, B = topo(rowConditions), topo(colConditions)
- if not A or not B: return []
- # 从拓扑序列中找到 val 的行列位置
- pos = [[0, 0] for _ in range(k + 1)]
- for idx, (k1, k2) in enumerate(zip(A, B)):
- pos[k1][0] = pos[k2][1] = idx
- # 填数字呀
- res = [[0] * k for _ in range(k)]
- for val, (x, y) in enumerate(pos[1:], 1):
- res[x][y] = val
-
- return res