LC周赛323题解

Posted on | Post modified:

LC周赛323题解

T1. 删除每行中的最大值

直接模拟即可

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
class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& a) {
        int n = (int)a.size();
        int m = (int)a[0].size();
        vector<vector<int> > vis(n, vector<int>(m, 0));
        int ans = 0 ;
        for(int s = 1; s <= m;  s++){
            int res = 0;
            for(int i = 0; i < n; i++){
                int rm = 0;
                int id = -1;
                for(int j = 0; j < m; j++){
                    if(!vis[i][j] && a[i][j] > rm){
                        rm = a[i][j];
                        id = j;
                    }
                }
                res = max(res, rm);
                vis[i][id] = 1;
            }
            ans += res;
        }
        return ans;
    }
};

T2. 数组中最长的方波

  • 排完序令$dp[v]$为以$v$结尾的方波最长的长度，则：$dp[v] = max(dp[v], dp[\sqrt{v}] + 1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dp[200001];
    int longestSquareStreak(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int v: nums) dp[v] = 1;
        int n =  (int)nums.size();
        for(int i = 1; i < n; i++){
            int q = (int)sqrt(nums[i]);
            if(q * q != nums[i]) continue;
            dp[nums[i]] = max(dp[nums[i]], dp[q] + 1);
        }
        int ans = 0;
        for(int v: nums) ans = max(ans, dp[v]);
        if(ans == 1) ans = -1;
        return ans;
    }
};

T3. 设计内存分配器

  • 暴力模拟
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
38
39
40
41
42
43
44
45
class Allocator {
public:
    int N;
    vector<vector<pair<int, int>> > g;
    set<pair<int, int>> l;
    Allocator(int n) {
        N = n;
        g.resize(1001);
    }

    
    int allocate(int size, int mID) {
        int ans = -1;
        for(int i = 0; i < N; i++){
            bool ok = 1;
            if(i + size - 1 > N - 1) continue;
            for(auto v: l){
                if(i + size - 1 < v.first) continue;
                if(i > v.second) continue;
                ok = false;
                break;
            }
            if(ok){
                ans = i;
                break;
            }
        }
        if(ans == -1) return -1;
        l.insert({ans, ans + size - 1});
        g[mID].push_back({ans, ans + size - 1});
        return ans;
    }
    
    int free(int mID) {
        for(auto v: g[mID]){
            l.erase(v);
        }
        int ans = 0;
        for(auto &v: g[mID]){
            ans += v.second - v.first + 1;
        }
        g[mID].clear();
        return ans;
    }
};

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

  • 将查询从小到大排序
  • 维护一个并查集，只连当前小于查询的边
  • 双指针维护即可
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
public:
    struct edge{
        int u, v, minn, maxx;
        bool operator<(const edge &other) const{
            if(maxx == other.maxx){
                return minn < other.minn;
            }
            return maxx < other.maxx;
        }
    };
    int fa[200001];
    int siz[200001];
    int find(int x){
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return ;
        fa[y] = x;
        siz[x] += siz[y];
    }
    vector<int> maxPoints(vector<vector<int>>& a, vector<int>& q) {
        int ss = (int)q.size();
        vector<pair<int, int>> qq(ss);
        for(int i = 0; i < ss; i++){
            qq[i] = {q[i], i};
        }
        sort(qq.begin(), qq.end(), [&](pair<int, int> a, pair<int, int> b){
            return a.first < b.first;
        });
        int n = (int)a.size();
        int m = (int)a[0].size();

        auto getid = [&](int x, int y){
            return x * m + y + 1;
        };
        auto check = [&](int x, int y) -> bool{
            return x >= 0 && x < n && y >= 0 && y < m;
        };
        vector<edge> E;
        int dir[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                for(int k = 0; k < 4; k++){
                    int ni = i + dir[k][0];
                    int nj = j + dir[k][1];
                    if(check(ni, nj)){
                        E.push_back({getid(i, j), getid(ni, nj), min(a[i][j], a[ni][nj]), max(a[i][j], a[ni][nj])});
                    }
                }
            }
        }
        
        sort(E.begin(), E.end());
        
        for(int i = 1; i <= n * m; i++){
            fa[i] = i;
            siz[i] = 1;
        }

        vector<int> ans(ss);
        int ptr = 0;
        for(int i = 0; i < (int)E.size();){
            if(ptr >= ss) break;
            if(E[i].maxx < qq[ptr].first){
                unite(E[i].u, E[i].v);
                i++;
            }else{
                if(qq[ptr].first <= a[0][0]){
                    ans[qq[ptr].second] = 0;
                }else{
                    ans[qq[ptr].second] = siz[find(1)];
                }
                ++ptr;
            }
        }
        if(ptr < ss){
            for(int i = ptr; i < ss; i++){
                if(qq[i].first <= a[0][0]){
                    ans[qq[i].second] = 0;
                }else{
                    ans[qq[i].second] = siz[find(1)];
                }                
            }
        }
        return ans;
    }
};