Biweekly Contest 12

Posted on | In , | |
Words count in article: 602 | Reading time ≈ 3

力扣排行榜

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
class Leaderboard {
public:
    map<int, int> a;
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        a[playerId] += score;
    }
    
    int top(int K) {
        vector<int> data;
        for (auto it = a.begin(); it != a.end();it++) {
            data.push_back(it->second);
        }
        sort(data.begin(), data.end());
        int ret = 0;
        for (int i = 0;i < K;i++) {
            ret += data[data.size() - i - 1];
        }
        return ret;
    }
    
    void reset(int playerId) {
        a[playerId] = 0;
    }
};

数组变换

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
class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        vector<int> a = arr;
        vector<int> b;
        int n = arr.size();
        while (1) {
            b = vector(n, 0);
            b[0] = a[0];
            b[n - 1] = a[n - 1];
            for (int i = 1;i < n - 1;i++) {
                if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
                    b[i] = a[i] + 1;
                }
                else if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                    b[i] = a[i] - 1;
                } else {
                    b[i] = a[i];
                }
            }
            if (a == b) {
                break;
            }
            a = b;
        }
        return a;
    }
};

树的直径

树的直径的解法，两次 BFS

  1. 任取一点 BFS，选择最长路径的节点，假设这个点为 a
  2. 从 aa= 开始 BFS，最长路径就是树的直径
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
class Solution {
public:
    //写个注释，返回值第一维代表最远的点，第二维代表start跟最远点的距离
    pair<int, int> bfs(vector<vector<int>>& e, int start) {
        vector<int> d(e.size(), -1);
        
        queue<int> Q;
        Q.push(start);
        d[start] = 0;
        
        pair<int, int> ret;
        
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            ret.first = x;
            ret.second = d[x];
            for (auto& y : e[x]) {
                if (d[y] == -1) {
                    d[y] = d[x] + 1;
                    Q.push(y);
                }
            }
        }
        return ret;
    }
    
    int treeDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> e(n, vector<int>());
        for (auto& edge: edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }
        
        pair<int, int> p;
        p = bfs(e, 0);
        p = bfs(e, p.first);
        
        return p.second;
    }
};

删除回文子数组

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 n, dp[105][105];
    int minimumMoves(vector<int>& arr) {
        n = (int)arr.size();
        for (int i = 1; i <= n; ++ i) 
            dp[i][i] = 1;
        
        for (int i = 1; i < n; ++ i) 
            dp[i][i + 1] = arr[i - 1] == arr[i] ? 1 : 2;
        
        for (int len = 3; len <= n; ++ len) {
            for (int i = 1; i + len - 1 <= n; ++ i) {
                int j = i + len - 1;
                dp[i][j] = j - i + 1;
                for (int k = i; k < j; ++ k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
                if (arr[i - 1] == arr[j - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }
        return dp[1][n];
    }
};
Donate? comment?