A

题目

2423. 删除字符使频率相同 - 力扣（LeetCode） (opens new window)

思路

1. 枚举 + STL

因为数据范围小，比赛时选择了比较好写的方法。

枚举删除每一位的情况，然后统计此时各个字母出现的次数的数量，用 map 统计(用数组也可以)，用 set 来判断不同次数的个数是否为 1 即可。

代码

​

B

题目

2424. 最长上传前缀 - 力扣（LeetCode） (opens new window)

思路

1. 暴力 + 性质

难点在于 upload() 的实现，但我们可以发现每次 upload 之后，其最长上传前缀并会减小，始终单调递增，因此维护一下最长上传前缀的结尾指针即可。

代码

class LUPrefix {
private:
  std::vector<bool> a;
  int res = 1;
public:
  LUPrefix(int n) {
      a.resize(n + 2);
  }
  
  void upload(int video) {
      a[video] = 1;
      while (a[res]) {
          res ++;
      }
  }
  
  int longest() {
      return res - 1;
  }
};

/**
* Your LUPrefix object will be instantiated and called as such:
* LUPrefix* obj = new LUPrefix(n);
* obj->upload(video);
* int param_2 = obj->longest();
*/

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

C

题目

2425. 所有数对的异或和 - 力扣（LeetCode） (opens new window)

思路

1.位运算 + 思维

首先我们要知道异或的一个性质：两个相同的数字异或的结果 0。

我们不难发现 nums1 中的每一个数字，在最终结果中会被异或 nums2.size() 次，而同理 nums2 中的每一个数字，在最终结果中会被异或 nums1.size() 次。而当一个数字进行偶数次异或之后，其值为 0，所以不会对结果产生影响；同时当一个数字进行了奇数次异或后，就相当于只进行了 1 次异或。因此如果 nums2.size() 为奇数时，我们将答案异或上 nums1 的每一个数字，而对 nums2 的每一位数字同理进行计算即可。

代码

class Solution {
public:
  int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
      int res = 0;
      int n = nums1.size(), m = nums2.size();
      if (m & 1) {
          for (auto x : nums1) {
              res ^= x;
          }
      }
      if (n & 1) {
          for (auto x : nums2) {
              res ^= x;
          }
      }
      return res;
  }
};

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

D

题目

2426. 满足不等式的数对数目 - 力扣（LeetCode） (opens new window)

思路

1. 树状数组 ， 为数组的范围，即数值最大值。

首先我们一下转化题目给定的等式 nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff，可得 nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff，我们再令 a[i] = nums1[i] - nums2[i]，可得 a[i] <= a[j] + diff

因此题目就转化成了，对于数组 a[i]，有多少个数对 (i, j) 满足 a[i] <= a[j] + diff 并且 0 <= i < j <= n - 1。

此时我们可以从前往后看，也就是对于下标 i，在它后面有多少个数满足上述条件，如果这样暴力做复杂度是 的，显然会 TLE。

因此，我们改为从后往前看，对于下标 j，在它前面有多少个数字满足 b[i] = a[i] - diff <= a[j]，此时我们可以很容易联想到 树状数组求逆序对。

但本题还有个问题，那就是数据中有负数存在的可能，因此我们要给每一个数字加一个偏移量，将所有数字映射到一个正数上即可，或者用离散化树状数组求解。

对于数字 nums1[i] - nums2[i] + diff 其值最小可以到 -3e4，因此我们需要给每一个 a[i] 加上 3e4 + 1。而此时数据的最大值可以达到 6e4 + 1，也就是原本的最大值 3e4 加上偏移量，所以树状数组我们则需要开至少 6e4 + 1 的空间。

我们从前往后遍历，对于 a[i] 答案每次都加上树状数组 [1, a[i]] 的和，也就是在 a[i] 前已经有多少个满足条件的值出现了，维护完答案后我们再更新树状数组，在 a[i] - diff 的地方加 1 即可。

代码

class Solution {
public:
  int t[60005];
  int m = 6e4 + 5;

  void add(int x, int c) {
      for (int i = x; i <= m; i += i & -i) 
          t[i] += c;
  }

  int sum(int x) {
      int res = 0;
      for (int i = x; i; i -= i & -i) 
          res += t[i];
      return res;
  }
  
  long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
      int n = nums1.size();
      std::vector<int> a(n);

      for (int i = 0; i < n; i ++) {
          a[i] = nums1[i] - nums2[i];
      }
      for (auto &x : a)
          x += 3e4 + 1;

      std::vector<int> b(n);
      for (int i = 0; i < n; i ++) {
          b[i] = a[i] - diff;
      }
      
      long long res = 0;
      for (int i = 0; i < n; i ++) {
          res += sum(a[i]);
          add(b[i], 1);
      }

      return res;
  }
};

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