A

题目

2389. 和有限的最长子序列 - 力扣（LeetCode） (opens new window)

思路

根据贪心，我们每次要选取尽可能小的数字才能保证长度最大，因此先从小到大对 进行排序，对于 我们从头开始选取 的元素，直到选取的元素之和不满足条件或数组遍历完结束，得到的长度就是最大长度。

代码

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        std::vector<int> res;
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        for (auto up : queries) {
            int sum = 0;
            int i = 0;
            for (i = 0; i < n; i ++) {
                sum += nums[i];
                if (sum > up) break;
            }
            if (i == n) res.push_back(n);
            else res.push_back(i);
        }
        return res;
    }
};

// Make sure to add code blocks to your code group

B

题目

2390. 从字符串中移除星号 - 力扣（LeetCode） (opens new window)

思路

模拟即可，遍历字符串 ，如果是非星号字符，则加入答案字符串，否则弹出答案字符串的最后一位即可。

代码

class Solution {
public:
  string removeStars(string s) {
      std::string res;
      for (auto c : s) {
          if (c != '*') {
              res += c;
          } else {
              res.pop_back();
          }
      }
      return res;
  }
};

// Make sure to add code blocks to your code group

C

题目

2391. 收集垃圾的最少总时间 - 力扣（LeetCode） (opens new window)

思路

对于 ，我们找出他们出现的最远位置，答案分别加上对应的 前缀和即可，最后将所有字符串的长度统计进答案即可。

代码

class Solution {
using ll = long long;
public:
  int garbageCollection(vector<string>& garbage, vector<int>& travel) {
      int n = garbage.size();
      std::vector<ll> psum(n);
      for (int i = 0; i < n - 1; i ++) {
          psum[i + 1] = psum[i] + travel[i]; 
      }
      ll res = 0; 
      std::map<char, bool> st;
      for (int i = n - 1; i > 0; i --) {
          for (auto c : garbage[i]) {
              if (st[c]) continue;
              res += psum[i];
              st[c] = 1;
          }
          if (st['G'] && st['M'] && st['P']) break;
      }
      for (auto s : garbage) {
          res += s.size();
      }
      return res;
  }
};

// Make sure to add code blocks to your code group

D

题目

2392. 给定条件下构造矩阵 - 力扣（LeetCode） (opens new window)

思路

假设仅考虑行的情况，我们可以对数字建一张图， 表示在数字 和 之间连一条有向边，不难发现其实就是进行拓扑排序。

对于列同理，因此我们先进行两次拓扑排序，然后对于数字 ，我们分别找出他在两次拓扑排序中的位置，并放入答案矩阵中即可。

如果出现拓扑排序失败的情况则说明无解。

代码

class Solution {
public:
  std::vector<int> toposort(int n, std::vector<std::vector<int>>& es) {
          std::vector<std::vector<int>> g(n + 1);
          std::vector<int> d(n + 1);
          for (auto& e: es) g[e[0]].push_back(e[1]), d[e[1]] ++ ;
          std::queue<int> q;
          for (int i = 1; i <= n; i ++)
              if (!d[i]) {
                  q.push(i);
              }
          
          std::vector<int> res;
          while (q.size()) {
              auto t = q.front();
              q.pop();
              res.push_back(t);
              
              for (int j: g[t])
                  if ( -- d[j] == 0)
                      q.push(j);
          }
          
          return res;
  }

  vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
      auto row = toposort(k, rowConditions);
      auto col = toposort(k, colConditions);
      if (row.size() < k || col.size() < k) return {};
      std::map<int, int> rpos, cpos;
      for (int i = 0; i < k; i ++) rpos[row[i]] = i, cpos[col[i]] = i;
      std::vector res(k, std::vector<int> (k));
      for (int i = 1; i <= k; i ++) {
          res[rpos[i]][cpos[i]] = i;
      }
      return res;
  } 
};

// Make sure to add code blocks to your code group