Skip to content

第 321 场周赛

比赛链接

Date: 2022-11-27

A 找出中枢整数

暴力 \(O(n^2)\) 或者等差数列求和 \(O(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int pivotInteger(int n) {
        for (int i = 1; i <= n; i++) {
            int x = (1 + i) * i / 2;
            int y = (i + n) * (n - i + 1) / 2;
            if (x == y) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
class Solution:
    def pivotInteger(self, n: int) -> int:
        for i in range(1, n + 1):
            if sum(range(1, i + 1)) == sum(range(i, n + 1)):
                return i
        return -1

复杂度分析

  • 时间复杂度：\(O(n)\) or \(O(n^2)\)
  • 空间复杂度：\(O(1)\)

B 追加字符以获得子序列

双指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int appendCharacters(string s, string t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        return t.size() - j;
    }
};

复杂度分析

  • 时间复杂度：\(O(\max(n, m))\)
  • 空间复杂度：\(O(1)\)

C 从链表中移除节点

单调栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        stack<ListNode*> stk;
        ListNode* t = head;
        while (t != nullptr) {
            while (stk.size() && stk.top()->val < t->val) {
                stk.pop();
            }
            stk.push(t);
            t = t->next;
        }
        auto it = stk.top();
        stk.pop();
        while (stk.size()) {
            auto pre = stk.top();
            pre->next = it;
            it = pre;
            stk.pop();
        }
        return it;
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

D 统计中位数为 K 的子数组

中位数为 \(k\) 的子数组（长度为 \(n\)）中，按照长度奇偶可以分为两种情况：

  • 偶数，小于 \(k\) 的个数等于 \(n/2 - 1\)，大于 \(k\) 的个数等于 \(n/2\)
  • 奇数，小于 \(k\) 的个数等于 \(\lfloor n/2\rfloor\)，大于 \(k\) 的个数等于 \(\lfloor n/2 \rfloor\)。

可以发现，不管奇偶，大于 \(k\) 的个数总是与小于 \(k\) 的个数相等或大于 \(1\)。

因此，找到 \(k\) 的位置 \(pos\)，遍历 \(pos\) 之前的每个位置 \(i\)，递推求解 \(i\sim pos\) 之间「大于 \(k\) 的数字个数减去小于 \(k\) 的数字个数」。而对于 \(pos\) 之后的位置也做同样计算，统计前后该个数加起来等于 0 或等于 1 的情况数即可。

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int pos = find(nums.begin(), nums.end(), k) - nums.begin();
        unordered_map<int, int> mp;
        int cur = 0;
        for (int i = pos; i >= 0; i--) {
            if (nums[i] < k) cur--;
            else if(nums[i] > k) cur++;
            mp[cur]++;
        }
        cur = 0;
        int res = 0;
        for (int i = pos; i < nums.size(); i++) {
            if (nums[i] < k) cur--;
            else if (nums[i] > k) cur++;
            res += mp[-cur] + mp[-cur + 1];
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)
本文访问 次