A

题目

2418. 按身高排序 - 力扣（LeetCode） (opens new window)

思路

1. 排序

新建一个 id 数组，然后按题意排序即可。

代码

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        std::vector<int> a(n);
        std::iota(a.begin(), a.end(), 0);
        sort(a.begin(), a.end(), [&](int i, int j) {
            return heights[i] > heights[j];
        });
        std::vector<std::string> res(n);
        for (int i = 0; i < n; i ++) {
            res[i] = names[a[i]];
        }
        return res;
    }
};

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

B

题目

2419. 按位与最大的最长子数组 - 力扣（LeetCode） (opens new window)

思路

1. 思维题 + 枚举

首先对于任一子数组的按位与的和，我们可以发现其值一定小于等于子数组中的最大值，当且仅当子数组所有数字相等时，取等号。

因此我们不难发现本题中，子数组最大的按位与和就是数组中的最大值，所以我们只需要先求出数组中的最大值 ，然后从开头进行枚举，求连续的 最长长度即可。

代码

class Solution {
public:
  int longestSubarray(vector<int>& nums) {
      int k = *max_element(nums.begin(), nums.end());
      
      int res = 1, i = 0, n = nums.size();
      while (i < n) {
          if (nums[i] == k) {
              int cnt = 1;
              i ++;
              while (i < n && nums[i] == k) {
                  cnt ++, i ++;
              }
              res = std::max(res, cnt);
          }
          i ++;
      }
      return res;
  }
};

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

C

题目

2406. 将区间分为最少组数 - 力扣（LeetCode） (opens new window)

思路

1.枚举

(这道题我在赛时过是过了，但写的太烦了...)

令 f[i] 表示以第 i 项作为结尾的最长非递增连续子序列，g[i] 表示以第 i 项作为开头的最长非递减连续子序列。

我们先预处理一遍后，在对 k <= i < n - k 的每一项判断是否满足好下标条件 f[i - 1] >= k && g[i + 1] >= k 即可

参考：枚举 - 找到所有好下标 - 力扣（LeetCode） (opens new window)

代码

class Solution {
public:
  vector<int> goodIndices(vector<int>& nums, int k) {
      int n = nums.size();
      std::vector<int> f(n), g(n);
      f[0] = 1, g[n - 1] = 1;
      for (int i = 1; i < n; i ++) {
          if (nums[i] <= nums[i - 1]) f[i] = f[i - 1] + 1;
          else f[i] = 1;
      }
      for (int i = n - 2; ~i; i --) {
          if (nums[i] <= nums[i + 1]) g[i] = g[i + 1] + 1;
          else g[i] = 1;
      }
      std::vector<int> res;
      for (int i = k; i < n - k; i ++) {
          if (f[i - 1] >= k && g[i + 1] >= k) res.emplace_back(i);
      }
      return res;
  }
};

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

D

题目

2421. 好路径的数目 - 力扣（LeetCode） (opens new window)

思路

1. 排序 + 并查集

这道题的思路有点类似于最小生成树的算法。我们先对所有的点按权值进行排序，然后假设一棵树，开始时还没有结点在上面，然后我们从前往后依次去遍历排完序的点，对于当前的结点 ，我们再去遍历与 相连的所有点，设当前遍历到的与 相连的点为 ，如果此时 与 在一个连通块中，或者 的权值大于 (等后面遍历到结点 的时候再讨论) 时，我们就先不进行讨论。我们只需要判断在 所处的连通块中有多少个权值等于 点的结点，此时一定可以满足好路径的条件，注意 也可能在一个连通块中。而这些集合的操作我们就用并查集来实现，对于每个集合，我们令集合中的某个最大值结点作为集合的主导结点，其长度 size[fx]，表示在 fx 主导的集合中，权值等于vals[fx]的结点个数，所以按照乘法原理，每次答案要加上 size[find(x)] * size[find(y)]。最后，我们更新答案后，还要将 与 相连，合并为一个连通块，并且将小的集合合并到大的上面

代码

class Solution {
public:
  int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
      int n = vals.size();
      std::vector<int> id(n), p(n), size(n, 1);
      std::vector<std::vector<int>> G(n);
      for (int i = 0; i < n; i ++) p[i] = id[i] = i;
      
      std::sort(id.begin(), id.end(), [&](int i, int j) {
          return vals[i] < vals[j];
      });

      for (auto e : edges) {
          int u = e[0], v = e[1];
          G[u].emplace_back(v);
          G[v].emplace_back(u);
      }

      std::function<int(int)> find = [&](int x) { 
          return x == p[x] ? x : p[x] = find(p[x]); 
      };

      int res = n;

      for (int x : id) {
          int fx = find(x);
          for (int y : G[x]) {
              int fy = find(y);
              if (fy == fx || vals[y] > vals[x]) continue;
              if (vals[fy] == vals[x]) {
                  res += size[fy] * size[fx];
                  size[fx] += size[fy];
              }
              p[fy] = fx;
          }
      }
      return res;
  }
};

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