Skip to content

第 323 场周赛

比赛链接

Date: 2022-12-11

A 删除每行中的最大值

模拟题，C++ 每行一个优先队列，可以方便每次弹出最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        vector<priority_queue<int>> v(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                v[i].push(g[i][j]);
            }
        }
        int res = 0;
        for (int j = 0; j < m; j++) {
            int mx = 0;
            for (int i = 0; i < n; i++) {
                mx = max(mx, v[i].top());
                v[i].pop();
            }
            res += mx;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            grid[i] = [-x for x in grid[i]]
            heapify(grid[i])
        res = 0
        for i in range(len(grid[0])):
            mx = 0
            for q in grid:
                mx = max(mx, -heappop(q))
            res += mx
        return res

复杂度分析

  • 时间复杂度：\(O(nm\log m)\)
  • 空间复杂度：\(O(nm)\)

B 数组中最长的方波

动态规划，哈希

排序后，只能从前面的根号处转移，用哈希表记录它的位置即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestSquareStreak(vector<int>& a) {
        int n = a.size();
        sort(a.begin(), a.end());
        vector<int> d(n);
        unordered_map<int, int> mp;
        int res = 0;
        for (int i = 0; i < n; i++) {
            d[i] = 1;
            int s = sqrt(a[i]);
            if (s * s == a[i] && mp.count(s)) {
                d[i] = max(d[i], mp[s] + 1);
            }
            mp[a[i]] = d[i];
            res = max(res, d[i]);
        }
        if (res < 2) return -1;
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        n = len(nums)
        d = [0] * n
        h = {}
        nums.sort()
        res = 0
        for i, x in enumerate(nums):
            d[i] = 1
            q = int(math.sqrt(x))
            if q * q == x and q in h:
                d[i] = max(d[i], h[q] + 1)
            res = max(res, d[i])
            h[x] = d[i]
        return -1 if res < 2 else res

复杂度分析

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

C 设计内存分配器

直接用数组维护即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Allocator {
public:
    int n;
    vector<int> a;
    Allocator(int n) {
        this->n = n;
        a.resize(n);
    }

    int allocate(int size, int mID) {
        for (int i = 0, j = 0; i < n; i++) {
            if (a[i] != 0) continue;
            j = i;
            while (j < n && a[j] == 0) j++;
            if (j - i >= size) {
                for (int k = i; k < i + size; k++) {
                    a[k] = mID;
                }
                return i;
            } else {
                i = j;
            }
        }
        return -1;
    }

    int free(int mID) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == mID) {
                cnt++;
                a[i] = 0;
            }
        }
        return cnt;
    }
};

复杂度分析

  • 时间复杂度：\(O(nm + nq)\)，其中 \(n\) 是长度，\(m\) 是调用 \(allocate\) 的次数，\(q\) 是调用 \(free\) 的次数
  • 空间复杂度：\(O(n)\)

D 矩阵查询可获得的最大分数

将查询排序离线，然后用优先队列的广度优先搜索计算当前可以到达的位置个数

class Solution {
public:
    using TP = tuple<int, int, int>;
    static constexpr int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> v(n, vector<int>(m));
        vector<pair<int, int>> q;
        for (int i = 0; i < queries.size(); i++) {
            q.push_back({queries[i], i});
        }
        sort(q.begin(), q.end());

        priority_queue<TP, vector<TP>, greater<TP>> pq;
        pq.push(make_tuple(grid[0][0], 0, 0));
        v[0][0] = 1;

        int cur = 0;
        vector<int> res(q.size());
        for (int i = 0; i < q.size(); i++) {
            auto [cval, id] = q[i];
            while (pq.size()) {
                auto [val, x, y] = pq.top(); 
                if (val >= cval) break;
                pq.pop();
                cur++;
                for (int k = 0; k < 4; k++) {
                    int nx = x + dir[k][0], ny = y + dir[k][1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || v[nx][ny]) continue;
                    v[nx][ny] = 1;
                    pq.push(make_tuple(grid[nx][ny], nx, ny));
                }
            }
            res[id] = cur;
        }
        return res;
    }
};

复杂度分析

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

赛后小节，四个题都比较套路，T3如果用珂朵莉应该可以快一些，但是暴力也足够通过了。

本文访问 次