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

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

image.png

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

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

c++题解

第一题

class Solution {
public:
    string freqAlphabets(string s) {
        int p = 0, n = s.length(), tmp;
        string res = "";
        while(p < n) {
            if(p + 2 < n && s[p + 2] == '#') {
                tmp = (s[p] - '0') * 10 + s[p + 1] - '0';
                res += 'a' + tmp - 1;
                p += 3;
            }
            else {
                res += 'a' + s[p] - '1';
                p++;
            }
        }
        return res;
    }
};

第二题

注意到异或计算的性质 a ^ b ^ a = b

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

第三题

先bfs找到level,统计就行了

bool cmp(const pair<string, int>& a, const pair<string, int>& b)
{
    return a.second < b.second || (a.second == b.second && strcmp(a.first.c_str(), b.first.c_str()) < 0);
}

class Solution {
public:
    void bfs(vector<vector<int>>& friends, int id, vector<int>& b, int up) {
        queue<int> q;
        int m = 1, x, level = 0;
        q.push(id);
        while(m > 0) {
            if(level == up) return;
            level++;
            while(m--) {
                x = q.front();
                q.pop();
                for(auto y : friends[x])
                    if(b[y] == -1) {
                        b[y] = level;
                        q.push(y);
                    }
            }
            m = q.size();
        }
        return;
    }
    
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = friends.size();
        vector<int> b(n, -1);
        b[id] = 0;
        bfs(friends, id, b, level);
        unordered_map<string, int> cnt;
        for(int i = 0; i < n; i++)
            if(b[i] == level)
                for(auto s : watchedVideos[i]) {
                    if(cnt.count(s) == 0) cnt[s] = 0;
                    cnt[s]++;
                }
        vector<pair<string, int>> k(cnt.begin(), cnt.end());
        sort(k.begin(), k.end(), cmp);
        vector<string> res;
        for(auto p : k) res.push_back(p.first);
        return res;
    }
};

第四题

上LCS,代码写起来最快吧

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