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

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

image.png

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

展开讨论

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
展开全部 12 讨论