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

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

image.png

3 分 - 检查整数及其两倍数是否存在
4 分 - 制造字母异位词的最小步骤数
5 分 - 推文计数
7 分 - 参加考试的最大学生数

展开讨论

检查整数及其两倍数是否存在

思路

  1. 参考第一题 two-sum

答题

bool checkIfExist(vector<int>& arr) 
{
    set<int> s;
    for (auto n : arr)
    {
        if (s.count(n * 2) != 0) return true;
        if ((n % 2 == 0) && s.count(n / 2) != 0) return true;
        s.insert(n);
    }
    return false;
}

制造字母异位词的最小步骤数

思路

  1. 统计 s 和 t 的字母个数
  2. 计算出 s 有而 t 缺失的字母个数

答题

int minSteps(string s, string t) 
{
    vector<int> char_s(26, 0);
    vector<int> char_t(26, 0);
    for (auto c : s)
    {
        char_s[c - 'a']++;
    }
    for (auto c : t)
    {
        char_t[c - 'a']++;
    }
    int ans = 0;
    for (int i = 0; i < 26; i++)
    {
        ans += (char_s[i] > char_t[i]) ? char_s[i] - char_t[i] : 0;
    }
    return ans;
}

推文计数

思路

  1. 使用 map<int, int> 来保存某时间点的推文数量
  2. 这样是按时间排序的,并且可以使用 lower_bound 来二分查找

答题

class TweetCounts {
public:
    TweetCounts() {}
    
    void recordTweet(string tweetName, int time) 
    {
		record[tweetName][time]++;
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)
    {
		int f = 1;
		f *= (freq == "minute") ? 60 : 1;
		f *= (freq == "hour") ? 60 * 60 : 1;
		f *= (freq == "day") ? 60 * 60 * 24 : 1;

		vector<int> ans;
		int t = startTime;
		while (t <= endTime)
		{
			auto bg = record[tweetName].lower_bound(t);
			auto ed = record[tweetName].upper_bound(min(t + f - 1, endTime));
			int cnt = 0;
			for (auto it = bg; it != ed; it++)
			{
				cnt += it->second;
			}
			ans.push_back(cnt);
			t += f;
		}
		return ans;
    }

private:
	unordered_map<string, map<int, int>> record;
};

参加考试的最大学生数

思路

  1. 对每一行的座位安排进行状态压缩
  2. 检测其座椅是否正常,以及学生是否相邻
  3. 对于合法的座位安排,可以计算出这一行能安排的学生数量
  4. 学生相邻检测,除了本行之内的,仅与上一行相关
  5. 对于上一行和这一行的所有安排组合之后的合法安排,可以保存各种组合的最大值
  6. 令 dp[i][j] 表示第 i 行的 j 种安排方式下,前 i 行能安排的学生数量
  7. 那么第 i 行的 j 种安排方式的数量就等于 i - 1 行所有合法排列中最大的数量 + 第 i 行的学生数量
  8. 即:dp[i][j]=max(dp[i][j],dp[i−1][k]+counti)dp[i][j] = max(dp[i][j], dp[i-1][k] + count_i)

答题

class Solution {
public:
	int getCount(int n)	// 这种安排下的人数
	{
		bitset<8> bs(n);
		return bs.count();
	}

	bool checkChair(vector<vector<char>>& seats, int row, int n)
	{	// 检查椅子是否正常
		bitset<8> bs(n);
		for (int i = 0; i < seats[row].size(); i++)
		{
			if (seats[row][i] == '#' && bs[i] == 1) return false;
		}
		return true;
	}

	bool checkValid(int n)
	{	// 检查左右是否相邻,如果传入 j | k 可以根据题意检测两行是否相邻
		bitset<8> bs(n);
		for (int i = 1; i < 8; i++)
		{
			if (bs[i] == 1 && bs[i - 1] == 1) return false;
		}
		return true;
	}

	int maxStudents(vector<vector<char>>& seats)
	{
		int ans = 0;
		vector<vector<int>> dp(seats.size(), vector<int>(1 << seats[0].size(), 0));

		for (int i = 0; i < seats.size(); i++)
		{
			for (int j = 0; j < (1 << seats[0].size()); j++)
			{
				if (!checkChair(seats, i, j)) continue;
				if (!checkValid(j)) continue;
				int cnt = getCount(j);
				if (i == 0)
				{
					dp[i][j] = cnt;
				}
				else
				{
					for (int k = 0; k < (1 << seats[0].size()); k++)
					{
						if (!checkValid(j | k)) continue;
						dp[i][j] = max(dp[i][j], dp[i - 1][k] + cnt);
					}
				}
				ans = max(ans, dp[i][j]);
			}
		}
		return ans;
	}
};

致谢

第四题是赛后学习 @newbie 的题解,感觉清晰易懂。

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

2
展开全部 42 讨论