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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2019-11-02
最近编辑于 2019-11-02

12 双周赛题解

5097. 力扣排行榜

由于数据范围:

1playerId,K1041 \leq playerId, K \leq 10^4

所以应该直接暴力就行。为了避免 Python 的坑,用优先队列优化了一下 topK 求和,用一个字典优化了存在性判断。

class Leaderboard:

    def __init__(self):
        self.heap = []
        self.hasId = {}

    def addScore(self, playerId: int, score: int) -> None:
        if self.hasId.get(playerId, False) == False:
            heapq.heappush(self.heap, (-score, playerId))
            self.hasId[playerId] = True
        else:
            for i, n in enumerate(self.heap):
                if n[1] == playerId:
                    self.heap[i] = (self.heap[i][0] - score, playerId)
        #print(self.heap)
        

    def top(self, K: int) -> int:
        topK = heapq.nsmallest(K, self.heap)
        res = 0
        for i in topK:
            res += -i[0]
        return res    
        

    def reset(self, playerId: int) -> None:
        for i, n in enumerate(self.heap):
            if n[1] == playerId:
                self.hasId[playerId] = False
                del self.heap[i]
                return None

5096. 数组变换

根据题目暴力就行

class Solution:
    def transformArray(self, arr: List[int]) -> List[int]:
        import copy
        while True:
            new = copy.deepcopy(arr)
            for ind, n in enumerate(arr):
                if ind == 0 or ind == len(new) - 1: 
                    continue
                if arr[ind] > arr[ind - 1] and arr[ind] > arr[ind + 1]:
                    new[ind] -= 1 
                elif arr[ind] < arr[ind - 1] and arr[ind] < arr[ind + 1]:
                    new[ind] += 1    
            if new == arr:
                return new
            arr = new
        return []    

5098. 树的直径

就是求一个图的最长路径,之前在 HDU 上有个收集糖果的题目类似,那个是求最长路径上的节点数,那其实就是 最长路径 + 1 ,而这题是裸题。为了避免 python 在写图论时候的坑,用 cpp 写了一版 dfs A 了:

class Solution {
public:
    vector<int> e[10004];
    int vis[10004] = {0};
    int ans = 0, now = 1;
    void dfs(int u,int dis){
        if(ans < dis) {
            ans = dis;
            now = u;
        }
        vis[u] = 1;
        for(int i = 0; i < e[u].size(); ++ i) {
            int v = e[u][i];
            if (!vis[v])
                dfs(v, dis + 1);
        }
    }

    int treeDiameter(vector<vector<int>>& edges) {
        for (int i = 0; i < edges.size(); ++ i) {
            int a = edges[i][0];
            int b = edges[i][1];
            e[a].push_back(b);
            e[b].push_back(a);
        }
        dfs(1, 0);
        ans = 0;
        memset(vis, 0, sizeof(vis));
        dfs(now, 0);
        return ans;
    }
};

5115. 删除回文子数组

比赛的时候没有做出来。看了这篇题解,发现就是一个区间 dp。

  1. dp[l][r] 代表 [l, r] 删除的操作数,所以我们枚举分隔点 k,然后 dp[l][r] 自然就从 dp[l][k] + dp[k + 1][r] 转移过来;
  2. 如果 arr[l] == arr[r],那么其实就从 dp[l + 1][r - 1] 转移而来,因为范围 [l + 1, r - 1] 里面不管怎么删除,lr 位置的字母具有回文性,删除里面的串,外部就可以通过一步干掉。

时间复杂度 O(n^3)。另外,相同思路代码用 Python 可能会 TLE,不解为什么。

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


最后,欢迎大家关注我的微信公众号,算法 + iOS 移动开发,全是干货!

image.png

4
展开全部 12 讨论