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

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

image.png

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

展开讨论

发个题解~周赛170

这次周赛也算简单。46分钟完成,可能是我个人最快的记录,但是也排到了全国65、全球329名了。

第一次写题解,大家有什么意见或者疑问,欢迎留言。

1、解码字母到整数映射

贪心:线性遍历,优先检查“10#~26#”,如果不是则为“1~9”。

class Solution {
public:
    string freqAlphabets(string s) {
        string res;
        const int n = s.size();
        for (int i = 0; i < n; ) {
            if (i + 2 < n && s[i + 2] == '#') {
                int m = 0;
                m = m * 10 + s[i] - '0';
                m = m * 10 + s[i + 1] - '0';
                res += 'a' + m - 1;
                i += 3;
            } else {
                res += s[i] - '0' + 'a' - 1;
                i += 1;
            }
        }
        return res;
    }
};

2、子数组异或查询

使用前缀和,不过这里是前缀XOR。在前缀和中,求数组时累加nums[i],求区间时相减prefix[i] - prefix[j];那么在前缀XOR中,相当于XOR同时表示了这个“加”“减”的过程。

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        const int n = arr.size();
        vector<int> prefix = {0};
        for (int a : arr) {
            prefix.push_back(prefix.back() ^ a);
        }

        vector<int> res;
        for (auto query : queries) {
            res.push_back(prefix[query[1] + 1] ^ prefix[query[0]]);
        }
        return res;
    }
};

3、获取你好友已观看的视频

  1. 进行层次遍历(BFS)
  2. 排序
/**
 * 1、先根据朋友圈关系来建图
 * 2、进行层次遍历(BFS)
 * 3、排序
 */

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        // BFS
        unordered_set<int> visit;
        vector<int> currs;
        currs.push_back(id);
        visit.insert(id);
        for (int l = 0; l < level && currs.size() > 0; ++l) {
            vector<int> nexts;
            for (int i : currs) {
                for (int j : friends[i]) {
                    if (!visit.count(j)) {
                        visit.insert(j);
                        nexts.push_back(j);
                    }
                }
            }
            currs = nexts;
        }

        // 找到对应的video、并排序
        unordered_map<string, int> videoFreq;
        for (int i : currs) {
            for (string &v : watchedVideos[i]) {
                ++videoFreq[v];
            }
        }
        vector<string> res;
        for (auto p : videoFreq) {
            res.push_back(p.first);
        }
        sort(res.begin(), res.end(), [&](const string &v1, const string &v2) {
            if (videoFreq[v1] != videoFreq[v2]) return videoFreq[v1] < videoFreq[v2];
            return v1 < v2;
        });

        return res;
    }
};

4、让字符串成为回文串的最少插入次数

对于回文子串问题,最常见的解法是“中心扩展”。举个例子s = "abca",如果以c(2)为中心来向两边扩展,发现b(1) != a(3),这时候我有两种选择:

  • 左补:在c(2)左边补一个a,来配对右边的a(3)。然后下一次探测,左边到达b(1),右边到达字符串结尾(4)
  • 右补:在c(2)右边补一个b以配对左边的b(1)。在下一次探测中,左边到达a(0),右边到达a(3)

可以看到,选择不同的策略会影响之后的局势,所以这是个DP问题。这里提供一个Top-down DP的解法。

class Solution {
public:
    int minInsertions(string s) {
        str = s;
        const int n = str.size();
        cache = vector<vector<int>>(n, vector<int>(n, -1));

        int res = n;
        for (int i = 0; i < str.size(); ++i) {
            res = min(res, helper(i, i)); // 奇回文
            if (i + 1 < str.size()) {
                res = min(res, helper(i, i + 1)); // 偶回文
            }
        }
        return res;
    }

    int helper(int i, int j) {
        if (i < 0) return str.size() - j;
        if (j >= str.size()) return i + 1;
        
        if (cache[i][j] != -1) return cache[i][j];

        int res = 0;
        if (str[i] == str[j]) { // 相等,则匹配
            res += helper(i - 1, j + 1);
        } else { // 不相等,要么左匹配,要么右匹配
            int left = helper(i - 1, j);
            int right = helper(i, j + 1);
            res += 1 + min(left, right);
        }
        return cache[i][j] = res;
    }

private:
    string str;
    vector<vector<int>> cache;
};
2
展开全部 12 讨论