讨论/题目交流/🏆 第 170 场力扣周赛/
🏆 第 170 场力扣周赛

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

image.png

3 分 - 解码字母到整数映射
5 分 - 子数组异或查询
5 分 - 获取你好友已观看的视频
7 分 - 让字符串成为回文串的最少插入次数

展开讨论
力扣 (LeetCode)发起于 2020-01-05

第一题
没什么好说的,由于#有优先级,所以倒过来跑一遍就好了,最后反转那个[::-1]有点妙

class Solution(object):
    def freqAlphabets(self, s):
        """
        :type s: str
        :rtype: str
        """
        out = ''
        n = len(s)-1
        while (n >= 0):
            if s[n] == '#':
                out = out + chr(96+eval(s[n-2:n]))
                n -= 3
            else:
                out = out + chr(96+eval(s[n]))
                n -= 1
        return out[::-1]

第二题
也很简单,xor具有前缀和性质

class Solution(object):
    def xorQueries(self, arr, queries):
        """
        :type arr: List[int]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        n = len(arr)
        for i in range(1, n):
            arr[i] = arr[i] ^ arr[i-1]
        
        ans = []
        for p, q in queries:
            if p == 0:
                ans.append(arr[q])
            else:
                ans.append(arr[q] ^ arr[p-1])
        return ans

第三题
一开始看题目描述叽里呱啦一大堆,就先去做第四题了
其实就BFS一下,然后拿个dict/map记录然后排下序就完事了

class Solution(object):
    def watchedVideosByFriends(self, watchedVideos, friends, id, level):
        """
        :type watchedVideos: List[List[str]]
        :type friends: List[List[int]]
        :type id: int
        :type level: int
        :rtype: List[str]
        """
        n = len(watchedVideos)
        Dist = list([-1] * n)
        
        Dist[id] = 0
        q = [id]
        
        while (len(q) > 0):
            x = q[0]
            q = q[1:]
            for v in friends[x]:
                if Dist[v] == -1:
                    q.append(v)
                    Dist[v] = Dist[x]+1
        
        Dict = dict()
        for i in range(n):
            if Dist[i] == level:
                for v in watchedVideos[i]:
                    if v in Dict:
                        Dict[v] += 1
                    else:
                        Dict[v] = 1
        
        out = sorted(Dict.items(), key = lambda kv:(kv[1], kv[0]))
        result = []
        for p, q in out:
            result.append(p)
        return result

第四题
没仔细想,想着把字符串反过来做一遍最长公共子串,好像就可以得到答案了
结果python for循环又给坑超时
只好重写一遍c++,又不小心写错了一个下标,罚时10分钟从12掉到30多,难顶

class Solution {
public:
    int minInsertions(string s) {
        int n = s.length();
        int f[n+1][n+1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (s[i-1] == s[n-j])
                    f[i][j] = f[i-1][j-1]+1;
                else {
                    f[i][j] = max(max(f[i-1][j], f[i][j-1]), f[i-1][j-1]);
                }
        return n - f[n][n];
    }
};
1
展开全部 12 讨论