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

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

image.png

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

展开讨论

。。。兄弟们,抢头条了。。。

第一题:

看看数据范围,1<=playerId,K<=100001 <= playerId, K <= 10000 那是坑人的,最多 10001000 次函数调用,KK 还比当前人数小,KK 真实的范围应该是 K<=1000K <= 1000
这数据范围,直接暴力都行

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;
    }
};

如果这题的数据范围大一点,咋做?树状数组可以考虑一下


第二题:

根据题意暴力。。。

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,选择最长路径的节点,假设这个点为 aa
  2. aa 开始 BFS,最长路径就是树的直径

当然也可以选择用 DFS 做,不过这个题数据范围 n<=10000n<=10000,在 stack overflow 的边缘,保险一点,我还是不敢选择用 DFS 做

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;
    }
};

第四题:

这题使我联想到那个消消乐的题,消消乐是相同颜色的一起消除,这题是消除回文串

同样是典型的区间 dp

dp[left][right]dp[left][right] 表示区间 [left,right][left, right] 删除完的最少操作

那么我们考察 arr[left]arr[left] 这个元素,这个元素要么自己删除,要么跟另一个等于 arr[left]arr[left] 的元素一起删除

假设 arr[left]=arr[i]arr[left] = arr[i],那么 leftleft 可以跟 ii 一起删除,这时候的操作数就是 max(dp[left+1][i1],1)+dp[i+1][right]max(dp[left + 1][i - 1], 1) + dp[i + 1][right]

第二项好理解,第一项为啥是 max(dp[left+1][i1],1)max(dp[left + 1][i - 1], 1),因为 leftleftii 可以跟 [left+1,i1][left+1,i-1] 里面某个回文数一起删除,如果 [left+1,i1][left+1,i-1] 本身是个空集,那么 leftleftii 一起删除,就是一次操作

ok,dp[left][right]dp[left][right] 就是枚举所有的跟 arr[left]arr[left] 相等的 arr[i]arr[i],对每个i计算一个操作数,求最小即可

class Solution {
public:
    int dp[102][102];
    int getdp(vector<int>& arr, int left, int right) {
        if (left == right) {
            return 1;
        }
        if (left > right) {
            return 0;
        }
        if (left + 1 == right && arr[left] == arr[right]) {
            return 1;
        }
        if (left + 1 == right && arr[left] != arr[right]) {
            return 2;
        }
        if (dp[left][right] != -1) {
            return dp[left][right];
        }
        int ret = 0x3fffffff;
        
        for (int i = right;i >= left;i--) {
            if (arr[left] != arr[i]) {
                continue;
            }
            int t = getdp(arr, left + 1, i - 1);
            if (t == 0) {
                t = 1;
            }
            ret = min(ret, t + getdp(arr, i + 1, right));
        }
        return dp[left][right] = ret;
    }
    int minimumMoves(vector<int>& arr) {
        memset(dp, -1, sizeof(dp));
        return getdp(arr, 0, arr.size() - 1);
    }
};
21
展开全部 12 讨论