A

题目

2404. 出现最频繁的偶数元素 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

用数组或者哈希表统计每个数字出现的次数，然后枚举以此判断即可

代码

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        std::map<int, int> cnt;
        for (auto x : nums) cnt[x] ++;
        int maxcnt = -1, maxv = -1;
        for (auto [x, cc] : cnt) {
            if (x % 2 == 0 && cc > maxcnt) maxv = x, maxcnt = cc;
        }
        return maxv;
    }
};

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

B

题目

2405. 子字符串的最优划分 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

从头往后枚举

代码

class Solution {
public:
  int partitionString(string s) {
      int res = 0;
      std::vector<bool> pos(26);
      for (auto x : s) {
          if (pos[x - 'a']) {
              res ++;
              for (int i = 0; i < 26; i ++) pos[i] = 0;
              pos[x - 'a'] = 1;
          } else {
              pos[x - 'a'] = 1;
          }
      }
      return res + 1;
  }
};

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

C

题目

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

思路

1.贪心 + 优先队列

先对序列按左端点进行排序，然后用小根堆维护最小的右端点，每次取最小的右端点和当前的区间进行比较。如果没有相交，就取出堆顶并放入当前区间的右端点，表示合并到一个组中；否则有相交，则直接入堆当前区间的右端点即可。最终答案便是优先队列的长度。

代码

class Solution {
public:
  int minGroups(vector<vector<int>>& intervals) {
      std::sort(intervals.begin(), intervals.end());
      int n = intervals.size();
      std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
      for (int i = 0; i < n; i ++) {
          if (pq.empty() || pq.top() >= intervals[i][0]) pq.emplace(intervals[i][1]);
          else {
              pq.pop();
              pq.emplace(intervals[i][1]);
          }
      }
      return pq.size();
  }
};

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

2.差分

通过差分，可以用 的时间进行区间修改，对任意区间 ，我们令 差分数组 dif[left] ++, dif[right + 1] --;。由于差分数组的前缀和等于单点的值，我们只需要遍历差分数组求前缀和，便能得到每个点的区间重叠个数，答案取其最大值即可

代码

class Solution {
public:
  int minGroups(vector<vector<int>>& intervals) {
      int n = intervals.size();
      std::vector<int> dif(1e6 + 2);

      for (auto x : intervals) {
          dif[x[0]] ++, dif[x[1] + 1] --;
      }
      int res = 0, sum = 0;

      for (auto x : dif) {
          res = std::max(res, sum += x);
      }
      return res;
  }
};

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

D

题目

2407. 最长递增子序列 II - 力扣（LeetCode） (opens new window)

思路

前置题：300. 最长递增子序列 - 力扣（LeetCode） (opens new window)

1. DP + 线段树优化

前置题是一道 的裸题，不用优化的 ，时间复杂度是 。我们也可以通过二分并维护一个有序队列进行解题，时间复杂度是 。而对 可以用线段树进行优化，因为我们每次找的是前面的数中的最大值，所以可以用线段树维护区间最大值，将时间复杂度优化到 ，不过对于有负数的情况需要进行离散化。

而本题便是基于 的 + 线段树优化来求解的，我们只需更改状态转移的条件为 严格递增并且差值不超过 即可。

代码

class Solution {
public:
using ll = long long;
  std::vector<int> max;
  void modify(int u, int l, int r, int pos, int val) {
      if (l == r) max[u] = val;
      else {
          int mid = (l + r) >> 1;
          if (pos <= mid) modify(u << 1, l, mid, pos, val);
          else modify(u << 1 | 1, mid + 1, r, pos, val);
          max[u] = std::max(max[u << 1], max[u << 1 | 1]);
      }
  }

  int query(int u, int l, int r, int L, int R) {
      if (L <= l && r <= R) return max[u];
      int res = 0;
      int mid = (l + r) >> 1;
      if (L <= mid) res = query(u << 1, l, mid, L, R);
      if (R > mid) res = std::max(res, query(u << 1 | 1, mid + 1, r, L, R));
      return res;
  }

  int lengthOfLIS(vector<int>& nums, int k) {
      int n = nums.size();
      int mx = *max_element(nums.begin(), nums.end());
      max.resize(mx * 4 + 10);
      for (int i = 0; i < n; i ++) {
          if (nums[i] == 1) modify(1, 1, mx, 1, 1);
          else {
              int maxv = query(1, 1, mx, std::max(1, nums[i] - k), nums[i] - 1) + 1;
              modify(1, 1, mx, nums[i], std::max(1, maxv));
          }
      }
      return max[1];
  }
};

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