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

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

image.png

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

展开讨论
共 12 个讨论

第一题:

这种解密题的难度就是寻找解密的顺序的。不过这个题很容易看出来,先解密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

哈,第一次进前十。有点小激动。

5

1. 解码字母到整数映射

思路

  1. 从后往前解析
  2. 以'#'为标志位区分两种逻辑

答题

string freqAlphabets(string s)
{
    string ans;
    for (size_t i = s.size() - 1; i < s.size(); i--)
    {
        int n = s[i] - '0';
        if (s[i] == '#')
        {
            string t;
            t += s[i - 2];
            t += s[i - 1];
            n = stoi(t);
            i -= 2;
        }
        ans.push_back('a' - 1 + n);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

2. 子数组异或查询

思路

  1. 前缀异或

答题

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries)
{
	vector<int> res(arr.size(), 0);

	res[0] = arr[0];
	for (size_t i = 1; i < arr.size(); i++)
	{
		res[i] = res[i - 1] ^ arr[i];
	}

	vector<int> ans;
	for (auto qu : queries)
	{
		int left = (qu[0] == 0) ? 0 : res[qu[0] - 1];
		int r = (left == 0) ? res[qu[1]] : res[qu[1]] ^ left;
		ans.push_back(r);
	}
	return ans;
}

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

思路

  1. 使用 bfs 套路,获得第 level 层的好友
  2. 使用map<string, int>统计频率
  3. 使用multimap<int, string>转换为按照频率升序及字典序

答题

vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) 
{
	unordered_set<int> friend_set;
	friend_set.insert(id);
	vector<int> friend_vector = { id };

	for (int i = 0; i < level; i++)	// 仅用来计算次数
	{
		vector<int> temp;
		for (auto n : friend_vector)
		{
			for (auto cur : friends[n])
			{
				if (friend_set.count(cur) != 0) continue;
				friend_set.insert(cur);
				temp.push_back(cur);
			}
		}
		friend_vector = temp;
	}

	map<string, int> frequencies;	// 统计观看频率
	for (auto n : friend_vector)
	{
		for (auto v : watchedVideos[n])
		{
			frequencies[v]++;
		}
	}

	multimap<int, string> videos;	// 转换为按照频率升序及字典序
	for (auto n : frequencies)
	{
		videos.insert({ n.second, n.first });
	}

	vector<string> ans;	// 转换为输出格式
	for (auto m : videos)
	{
		ans.push_back(m.second);
	}
	return ans;
}

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

思路

同[516. 最长回文子序列]。

答题

int minInsertions(string s) 
{
	vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
	for (size_t i = s.size() - 1; i < s.size(); i--)
	{
		dp[i][i] = 1;
		for (size_t j = i + 1; j < s.size(); j++)
		{
			if (s[i] == s[j])
			{
				dp[i][j] = dp[i + 1][j - 1] + 2;
			}
			else
			{
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
	}
	return s.size() - dp[0].back();
}
2

发个题解~周赛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

第一题
没什么好说的,由于#有优先级,所以倒过来跑一遍就好了,最后反转那个[::-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

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

除了第2题不会,其他都还好.
第一题,建立字母和数字 #的映射, 也可以直接ord(n+96)), 检查 i+2位置是否为"#",然后分情况取数字对应的字母.
第二题一看异或,就知道肯定是有公式可用的,但我不知道-,-!
区间查询,一般是前缀和数组,如果有update,一般用树状数组.
第三题,图的层次遍历,一圈一圈,BFS.
第四题,长度-回文子序列长度.DP.

结果和答案一模一样还判WA,有点过分吧

第二题暴力也能过??

求助!!!

大家好!
第三题
我用下面的代码,用递归获取朋友列表,这么写提交的时候有不正确答案,有点懵,能否帮我分析一下,谢谢

        from collections import Counter
        my_fr = set()
        visited = set()
        visited.add(id)
        cnt = Counter()

        def find_friend_in_level(id_, d):
            if d == 0:
                my_fr.add(id_)
                return
            for f_id in friends[id_]:
                if f_id not in visited:
                    visited.add(f_id)
                    find_friend_in_level(f_id, d - 1)

        find_friend_in_level(id, level)
        for f in my_fr:
            cnt.update(watchedVideos[f])
        print(cnt.most_common())

        r = sorted((v, k) for k, v in cnt.items())
        return [v for _, v in r]