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

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

image.png

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

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

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

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

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