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

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

image.png

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

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

第一题:

这种解密题的难度就是寻找解密的顺序的。不过这个题很容易看出来,先解密x这种形式,再解密xx#这种形式会引发冲突,因此必须先解密xx#这种形式

class Solution {
public:
    string freqAlphabets(string s) {
        string ret = "";
        int i = 0;
        while (i < s.size()) {
            if (i + 2 < s.size() && s[i + 2] == '#') {
                int c = (s[i] - '0') * 10 + (s[i + 1] - '0');
                ret.push_back(char(c + 'a' - 1));
                i += 3;
            } else {
                int c = (s[i] - '0');
                ret.push_back(char(c + 'a' - 1));
                i += 1;
            }
        }
        return ret;
    }
};

第二题:

异或有个性质:a ^ b ^ a = b,因此这个题我们可以用前缀和来解决区间查询问题

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> data(arr.size() + 1, 0);
        for (int i = 0;i < arr.size();i++) {
            data[i + 1] = arr[i] ^ data[i];
        }
        vector<int> ret;
        for (auto& query: queries) {
            ret.push_back(data[query[1] + 1] ^ data[query[0]]);
        }
        return ret;
    }
};

第三题:

纯bfs,一开始第0层只有一个结点id,然后bfs level次得到第level层的结点,再统计这一层结点看的视频,根据视频的次数和视频的名字进行排序

class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        boolean[] visited = new boolean[friends.length];
        Arrays.fill(visited, false);
        Queue<Integer> Q = new LinkedList<>();
        Q.add(id);
        visited[id] = true;

        for (int i = 1;i <= level;i++) {
            int n = Q.size();
            for (int j = 0;j < n;j++) {
                int x = Q.poll();
                for (int y: friends[x]) {
                    if (visited[y]) {
                        continue;
                    }
                    visited[y] = true;
                    Q.add(y);
                }
            }
        }

        Map<String, Integer> counter = new HashMap<>();
        while (!Q.isEmpty()) {
            int x = Q.poll();
            for (String video: watchedVideos.get(x)) {
                counter.compute(video, (k, v) -> v == null ? 1 : v + 1);
            }
        }

        return counter.entrySet().stream().sorted(
                (x, y) -> {
                    if (x.getValue().intValue() == y.getValue().intValue()) {
                        return x.getKey().compareTo(y.getKey());
                    } else {
                        return x.getValue().compareTo(y.getValue());
                    }
                }
        ).map(x -> x.getKey()).collect(Collectors.toList());
    }
}

第四题:

其实就是lc-516,几乎一模一样,代码也是一模一样的。

令dp[a][b]为字符串s[a..b]得到回文字符串的最小添加数,那么有dp方程:

dp[a][b]=min(dp[a+1][b]+1,dp[a][b1]+1,dp[a+1][b1](s[a]==s[b]))dp[a][b] = min(dp[a + 1][b] + 1, dp[a][b - 1] + 1, dp[a + 1][b - 1] (s[a] == s[b]))

class Solution {
public:
    int getCache(string& s, vector<vector<int>>& cache, int i, int j) {
        if (i == j) {
            return 0;
        }
        if (i > j) {
            return 0;
        }
        if (cache[i][j] != -1) {
            return cache[i][j];
        }
        int ret = 0x3fffffff;
        ret = min(getCache(s, cache, i, j - 1) + 1, ret);
        ret = min(getCache(s, cache, i + 1, j) + 1, ret);
        if (s[i] == s[j]) {
            ret = min(getCache(s, cache, i + 1, j - 1), ret);
        }
        return cache[i][j] = ret;
    }
    int minInsertions(string s) {
        vector<vector<int>> cache(s.size(), vector<int>(s.size(), -1));
        return getCache(s, cache, 0, s.size() - 1);
    }
};
6
展开全部 12 讨论