讨论/题目交流/🐱 第 12 场夜喵双周赛/
🐱 第 12 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组变换
4 分 - 力扣排行榜
5 分 - 树的直径
7 分 - 删除回文子数组

展开讨论

被第二题题意绊倒了,因为题意卡了 11 个小时也是醉了。。。。。。。。
分享一下自己会写的几道题的题解。

第一题

按照题意模拟即可,所有人的分数用 multiset存一下即可省的排序

const int MAXN = 1e4 + 10;
class Leaderboard {
    int board[MAXN];
    multiset<int> s;
    multiset<int> :: iterator ite;
   public:
    Leaderboard() {
        memset(board, 0, sizeof(board));
        s.clear();
    }
    void addScore(int playerId, int score) {
       if(board[playerId]) s.erase(s.find(-board[playerId]));
       board[playerId] += score;
       s.insert(-board[playerId]);
    }

    int top(int K) {
        int sum = 0;
        for(ite = s.begin(); K--; ite++) 
            sum += *ite;
        return -sum;
    }

    void reset(int playerId) {
        s.erase(s.find(board[playerId]));
        board[playerId] = 0;
    }
};

第二题

仔细读题暴力即可

class Solution {
   public:
    vector<int> transformArray(vector<int>& arr) {
        if(arr.size() <= 2) return arr;
        bool flag = false;
        while(!flag) {
            bool flag1 = true;
            vector<int> temp = arr;
            for(int i = 1; i < arr.size() - 1; i++) {
                if(arr[i] < temp[i - 1] && arr[i] < temp[i + 1]){
                    arr[i] += 1;
                    flag1 = false;
                }
                if(arr[i] > temp[i - 1] && arr[i] > temp[i + 1]) {
                    arr[i] -= 1;
                    flag1 = false;
                }
            }
            if(flag1) flag = true;
        }
        return arr;
    }
};

第三题

树的直径裸题,用两边 BFS,第一遍从起点 BFS 找到最远的点,第二遍从最远的点 BFS 找到最长的距离

const int MAXN = 100010;
int len, point, top;  //记录直径,最远点
struct node {
    int to, next, w;
} edge[MAXN];
int dis[MAXN];  //记录距离
bool vis[MAXN];
int head[MAXN];

class Solution {
   public:
    void addEdge(int u, int v, int z) {
        edge[top].to = v;
        edge[top].w = z;
        edge[top].next = head[u];
        head[u] = top++;
    }
    void BFS(int s) {
        queue<int> qu;
        memset(dis, 0, sizeof(dis));
        vis[s] = 1;
        qu.push(s);
        while (!qu.empty()) {
            int x = qu.front();
            qu.pop();
            for (int i = head[x]; i != -1; i = edge[i].next) {
                int y = edge[i].to;
                if (!vis[y]) {
                    dis[y] = dis[x] + edge[i].w;
                    if (len < dis[y]) {
                        len = dis[y];
                        point = y;
                    }
                    vis[y] = 1;
                    qu.push(y);
                }
            }
        }
    }
    int treeDiameter(vector<vector<int>>& edges) {
        memset(head, -1, sizeof(head));
        for (auto e : edges) {
            addEdge(e[0], e[1], 1);
            addEdge(e[1], e[0], 1);
        }
        len = 0;
        memset(vis, 0, sizeof(vis));
        BFS(0);
        len = 0;
        memset(vis, 0, sizeof(vis));
        BFS(point);
        return len;
    }
};

第四题

太菜了,第四题不会。。。。。。

2
展开全部 12 讨论