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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-02-09
共 42 个讨论

第三题,python自测和提交结果不一样,是怎么回事?
还有是不是修复了以后把罚的时间还回来?
以及我十分好奇,还有200个人过了,都是怎么做到的。。。。

16

第二题,中文题干又又又错了……

中文 “字母异位词 指字母相同,但排列不同的字符串。”
英文“An Anagram of a string is a string that contains the same characters with a different** (or the same) **ordering.”

题目给的示例 4:

输出:s = "xxyyzz", t = "xxyyzz"
输出:0

9

T3 的测试有问题? 不能执行测试, 也看到其他人这么反映了.

然后直接提交的话, 第一个测试点 WA.

不晓得评测是什么版本的 Java, 我本地运行是没问题的..

5

先是未知错误,然后又测试执行结果和提交结果不一样?
QQ图片20200209111248.png

5

第三题有问题啊,
提交测评的 wa,但是我的输出在本地和使用在线测试都是对的,提交却得到了错的答案?

显示出错数据:

["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

显示我的输出:

[null,null,null,null,[3],[2,1],null,[2,1,1]]

显示预期输出

[null,null,null,null,[2],[2,1],null,[4]]

我本地执行和在线测试结果都是

[null,null,null,null,[2],[2,1],null,[4]]

与预期一致

如果把最后一个测试样例的 hour 换成 minute 才是测评输出的结果???

5

我想知道他们怎么A的哈哈

5

我的题解(前三题通过,第四题回溯超时,一起讨论)

先吐槽一下,第三题做的时候一直是”执行状态:未知错误“,好影响心情啊。。。

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

送分题,估计时间限制也很宽松,直接照着题意写了个 O(n2)O(n^2) 的暴力解法通过了。

bool checkIfExist(vector<int>& arr) {
    int N = arr.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j && arr[i] == 2 * arr[j]) {
                return true;
            }
        }
    }
    return false;
}

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

异位词的题目我们很熟悉了。比较两个单词是否是异位词,是用两个 map 分别统计两个词的字符出现的次数,比较每个字符出现的次数是否相等。

这道题是让 t 变换几个字符到 s,稍微转换一下思路。先统计 s 中每个字符出现的次数,然后看 t 中有多少字符能覆盖掉 s 中的这些字符。剩下覆盖不掉的,就是要进行替换的字符。

题目说明 s 和 t 只包含小写字母,可以用一个长度为 26 的数组代替 map 来做统计。

int minSteps(string s, string t) {
    vector<int> counter(26, 0);
    for (char c : s) {
        counter[c-'a']++;
    }
    for (char c : t) {
        counter[c-'a']--;
    }
    int sum = 0;
    for (int c : counter) {
        if (c > 0) {
            sum += c;
        }
    }
    return sum;
}

5334. 推文计数

这道题不知道线上出了什么问题,等了好久终于可以提交通过了。

首先,用 map<string, vector<int>> 类型保存所有的推文信息。每次要进行统计的时候,先把所有推文按时间排序,就可以进行二分搜索了。C++ 中有内置的二分搜索函数 lower_bound,很方便。

统计的流程如下:

第一步,所有推文按时间排序。

auto& tws = tweets[tweetName];
sort(tws.begin(), tws.end());

第二步,计算时间点序列,即所有时间间隔的左右两个端点。设时间间隔的数量为 nn 的话,一共就有 n+1n+1 个时间端点。前 nn 个点是 startTime + delta* i ,最后一个点是 endTime + 1。

vector<int> ts;
    for (int t = startTime; t <= endTime; t += delta) {
        ts.push_back(t);
    }
ts.push_back(endTime+1);

第三步,这 n+1n+1 个时间点每个在推文时间中做二分搜索。lower_bound 会找到数组中第一个大于等于 t 的位置。得到 n+1n+1 个数组中的位置。

vector<int> idx;
for (int t : ts) {
    int i = lower_bound(tws.begin(), tws.end(), t) - tws.begin();
    idx.push_back(i);
}

第四步,n+1n+1 个位置错位相减,计算相邻两个位置中间的差,得到每个时间间隔的推文数量。

vector<int> res;
for (int i = 1; i < idx.size(); i++) {
    res.push_back(idx[i] - idx[i-1]);
}
return res;

全部代码如下:

class TweetCounts {
public:
    TweetCounts() {
        
    }
    
    void recordTweet(string tweetName, int time) {
        tweets[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        auto& tws = tweets[tweetName];
        sort(tws.begin(), tws.end());
        int delta = get_interval(freq);
        vector<int> ts;
        for (int t = startTime; t <= endTime; t += delta) {
            ts.push_back(t);
        }
        ts.push_back(endTime+1);
        
        vector<int> idx;
        for (int t : ts) {
            int i = lower_bound(tws.begin(), tws.end(), t) - tws.begin();
            idx.push_back(i);
        }
        
        vector<int> res;
        for (int i = 1; i < idx.size(); i++) {
            res.push_back(idx[i] - idx[i-1]);
        }
        return res;
    }
    
    int get_interval(string& freq) {
        if (freq == "minute") {
            return 60;
        } else if (freq == "hour") {
            return 60 * 60;
        } else {
            return 60 * 60 * 24;
        }
    }
    
private:
    map<string, vector<int>> tweets;
};

5335. 参加考试的最大学生数

这一题我也没找到正确答案,写了回溯法超时了。这里写写我的思路吧。

回溯法的思路很简单,如果找到了一个好的座位,可以尝试坐或者不坐。如果坐了,就把座位的右侧、左下、右下的三个座位变成坏的,然后继续搜索。

这是回溯的解法,但是会超时:

int maxStudents(vector<vector<char>>& seats) {
    int M = seats.size();
    int N = seats[0].size();
    int mcount = 0;
    backtrack(seats, M, N, 0, 0, mcount);
    return mcount;
}

void backtrack(vector<vector<char>>& seats, int M, int N, int n, int count, int& mcount) {
    if (n == M * N) {
        mcount = max(mcount, count);
        return;
    }

    int i = n / N;
    int j = n % N;

    if (seats[i][j] == '#') {
        // 坏的座位只能不坐
        backtrack(seats, M, N, n+1, count, mcount);

    } else {
        // 好的座位
        // 情况1:选择坐!
        char b1 = '#';
        char b2 = '#';
        char b3 = '#';
        // 右侧、左下、右下先标记为坏的
        if (j < N-1) { 
            swap(seats[i][j+1], b1);
        }
        if (i < M-1 && j > 0) {
            swap(seats[i+1][j-1], b2);
        }
        if (i < M-1 && j < N-1) {
            swap(seats[i+1][j+1], b3);
        }
        // 回溯搜索
        backtrack(seats, M, N, n+1, count+1, mcount);
        // 把刚才标记的座位还原
        if (j < N-1) {
            swap(seats[i][j+1], b1);
        }
        if (i < M-1 && j > 0) {
            swap(seats[i+1][j-1], b2);
        }
        if (i < M-1 && j < N-1) {
            swap(seats[i+1][j+1], b3);
        }

        // 情况2:选择不坐!
        backtrack(seats, M, N, n+1, count, mcount);
    }
}

运行超时,发现不能通过的输入都是好座位很多,导致搜索空间太大。

有大佬说用 DP 能做,我回头再想想咋做的。。

4

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

思路

  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

线 上 事 故

2

第三题测试系统现在OK了

还是自己的代码有问题,区间划分错了,把[59,145]分成了[59,59],[60,119],[120,145],而没有按照题意分成[59,118],[119,145]。

比赛时主要是被评测系统的问题误导了,一直觉得是全局状态的问题,没有仔细检查自己的区间划分的对不对。如果换成是一个不返回错误原因的评测系统,反而倒是有可能检查出来的。

2