好久没打周赛了，这次比较简单，纯纯手速场，写的基本都是暴力，可能不是最优写法。

A

题目

2485. 找出中枢整数 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

利用等差数列求和公式枚举即可。

代码

class Solution {
public:
    int pivotInteger(int n) {
        for (int i = 1; i<= n; i++) {
            if ((1 + i) * i / 2 == (i + n) * (n - i + 1) / 2) {
                return i;
            }
        }
        return -1;
    }
};

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

B

题目

2486. 追加字符以获得子序列 - 力扣（LeetCode） (opens new window)

思路

1. 双指针 + 遍历一次

只需要找到字符串 t 在 字符串 s 的子序列中存在的最长前缀即可，因此我们利用双指针分别指向两个数组，看看 s 能满足的 t 的最长前缀，最后答案是 t 的长度减去能满足的最长前缀的长度。

代码

class Solution {
public:
  int appendCharacters(string s, string t) {
      int i = 0, j = 0;
      int n = s.size(), m = t.size();
      for (; i < n; i++) {
          if (s[i] == t[j]) {
              j++;
          }
      }
      return m - j;
  }
};

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

C

题目

2487. 从链表中移除节点 - 力扣（LeetCode） (opens new window)

思路

1.后缀最大值

比赛时写的代码，可能有点繁杂，也不是最优的，不过想法应该是比较简单的。

先用数组 a 将链表存起来，然后得到后缀最大值数组 sufmax，我们要保留的元素满足其右侧不存在一个比他大的元素，所以对于下标 i，如果 a[i] == sufmax[i]，我们就保留下标为 i 的元素，最后用链表存起来即可

代码

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
  ListNode* removeNodes(ListNode* head) {
      std::vector<int> a;
      while (head) {
          a.emplace_back(head->val);
          head = head->next;
      }
      int n = a.size();
      std::vector<int> sufmax(n);
      sufmax.back() = a.back();
      for (int i = n - 2; ~i; i--) {
          sufmax[i] = std::max(a[i], sufmax[i + 1]);
      }
      auto res = new ListNode();
      auto t = res;
      for (int i = 0; i < n; i++) {
          if (sufmax[i] == a[i]) {
              t->val = a[i];
              t->next = new ListNode();
              t = t->next;
          }
      }
      auto tt = res;
      while (tt->next != t) {
          tt = tt->next;
      }
      tt->next = nullptr;
      return res;
  }
};

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

D

题目

2488. 统计中位数为 K 的子数组 - 力扣（LeetCode） (opens new window)

思路

1. 等价转换 + 哈希表

赛时的写法太烦了，不过整体思路差不多，数组的每个元素进行转换，如果大于 k 则为 1，小于 k 则为 -1，等于 k 则为 0。

那么我们就可以将问题转化寻找满足条件的子数组个数，条件是如果子数组长度为奇数，则子数组和为 0，如果长度为 偶数，则子数组和为 1。

我的写法因为 unordered_map 不支持复杂的映射，所以只能用 map 来实现哈希表，整体时间复杂度会因为排序多一个

代码

class Solution {
public:
  int countSubarrays(vector<int>& nums, int k) {
      std::map<std::pair<int, int>, int> pos; 
      for (auto &x : nums) {
          if (x > k) x = 1;
          else if (x == k) x = 0;
          else x = -1;
      }
      
      int n = nums.size();
      std::vector<int> psum(n);
      psum[0] = nums[0];
      for (int i = 1; i < n; i++) {
          psum[i] = psum[i - 1] + nums[i];
      }
      int res = 0;
      for (int i = 0; i < n; i++) {
          int len = i + 1;
          int tozero = psum[i];
          int toone = psum[i] - 1;
          if (((len & 1) && psum[i] == 0) || ((len % 2 == 0) && psum[i] == 1)) {
              res++;
          }
          res += pos[{tozero, (len & 1) ^ 1}];
          res += pos[{toone, (len & 1)}];
          
          pos[{psum[i], (i + 1) & 1}]++;
      }
      return res;
  }
};

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

这里贴一下灵神的代码，比我的会高效简洁很多(%%%%)

等价转换（Python/Java/C++/Go） - 统计中位数为 K 的子数组 - 力扣（LeetCode） (opens new window)

很容易发现子数组一定是包含 k 的，因此可以从 k 的位置出发，向左向右进行延伸，这样更高效，而且更容易去判断长度的奇偶性，cnt[i] 如果 i 是 奇数，则一定是朝一个方向衍生了奇数个数字，偶数同理，（因为在这里排除了 k 的情况，所以只会 +1 -1）那么向一边衍生 cnt[i] 位，向另一边衍生 cnt[i] 位，加上中间的 k，数字个数一定是 2 * i + 1 个，也就是奇数，当另一边衍生 cnt[i + 1] 位时，则一定是偶数长度。

代码

class Solution {
public:
  int countSubarrays(vector<int> &nums, int k) {
      int pos = find(nums.begin(), nums.end(), k) - nums.begin(), n = nums.size();
      unordered_map<int, int> cnt;
      cnt[0] = 1; // i=pos 的时候 c 是 0，直接记到 cnt 中，这样下面不是大于就是小于
      for (int i = pos + 1, c = 0; i < n; ++i) {
          c += nums[i] > k ? 1 : -1;
          ++cnt[c];
      }

      int ans = cnt[0] + cnt[1]; // i=pos 的时候 c 是 0，直接加到答案中，这样下面不是大于就是小于
      for (int i = pos - 1, c = 0; i >= 0; --i) {
          c += nums[i] < k ? 1 : -1;
          ans += cnt[c] + cnt[c + 1];
      }
      return ans;
  }
};

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