Leetcode第309场周赛

Date: September 4, 2022
Difficulty: medium
Rate by others: ⭐⭐⭐⭐
Time consuming: 1h30min

题目链接

竞赛 - 力扣 (LeetCode)

题目解析

2399. 检查相同字母间的距离

class Solution {
    public:
        bool checkDistances(string s, vector<int>& distance) {
            vector<int> arr(26, -1);
            int n = s.size(), t;
            for (int i = 0; i < n; ++i) {
                t = s[i] - 'a';
                if (arr[t] == -1) arr[t] = i;
                else if (i - arr[t] - 1 != distance[t]) return false;
            }
            return true;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13

没什么可说的，简单模拟题。

2400. 恰好移动 k 步到达某一位置的方法数目

class Solution {
        static constexpr int MAXN = 1050;
        static constexpr int MOD = 1e9 + 7;
        vector<vector<int>> memo_;
    public:
        Solution(): memo_(MAXN, vector<int>(MAXN, -1)) {}
        int aux(int dis, int k) {
            dis = std::abs(dis);
            if (memo_[dis][k] != -1) return memo_[dis][k];
            if (dis > k) memo_[dis][k] = 0;
            else if (dis == k) memo_[dis][k] = 1;
            else memo_[dis][k] = aux(dis - 1, k - 1) + aux(dis + 1, k - 1);
            if (memo_[dis][k] > MOD) {
                memo_[dis][k] %= MOD;
            }
            return memo_[dis][k];
        }
        int numberOfWays(int startPos, int endPos, int k) {
            return aux(endPos - startPos, k);
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

力扣

看了一眼题解，发现真的是道数学题，自己没有推出来，没有想到去思考用排列组合的想法去做。其实就算想到组合数，自己可能也想不到用递推式的做法$O(k^2)$或者$O(k)$去求组合数，而且还需要求逆元，相比之下自己用记忆化搜索硬搞出来也挺不容易的。用记忆化搜索的一个关键在于首先是用距离表示减少变量，然后是负距离和正距离是等价的。

什么时候应该总结一下组合数、逆元这部分的知识。

2401. 最长优雅子数组

class Solution {
    public:
        int longestNiceSubarray(vector<int>& nums) {
            constexpr int MAXN = 1e5 + 5;
            constexpr int N = 31;
            vector<int> BITS(N);
            int t = 1;
            for (int i = 0; i < N; ++i) {
                BITS[i]= t;
                t <<= 1;
            }

            vector<int> memo(N, -1);
            int n = nums.size();
            int ans = 0, last = -1;
            for (int i = 0; i < n; ++i) {
                t = -1;
                for (int j = 0; j < N; ++j) {
                    if (nums[i] & BITS[j]) {
                        t = std::max(t, memo[j]);
                        memo[j] = i;
                    }
                }
                last = std::max(t, last);
                ans = std::max(ans, i - last);
            }
            return ans;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

自己的思路总体上没有什么问题，就是滑动窗口，每次将左边窗口移动到元素最近的&不为0的位置的后面，这个区间内右边元素和区间内的元素&都是0，但是不能保证在这个区间内前面的元素&为0，需要保存元素的最右左区间，也就是说在这个区间任意两个元素&都为0，也就是优雅子区间。

看了一下其他人的写法，发现自己可以复用左区间的位置，当时还是对题目的理解不够深刻。

2402. 会议室 III

class Solution {
    public:
        int mostBooked(int n, vector<vector<int>>& meetings) {
            using ll = long long;
            vector<vector<ll>> room(n);
            sort(meetings.begin(), meetings.end(), [&](auto &&a, auto &&b) {
                return a[0] < b[0];
            });
            for (auto &&meeting : meetings) {
                bool flag = false;
                for (int i = 0; i < n; ++i) {
                    if (room[i].empty() || meeting[0] >= room[i].back()) {
                        room[i].push_back(meeting[1]);
                        flag = true;
                        break;
                    }
                }
                if (flag) continue;
                ll minT = room[0].back();
                int minI = 0;
                for (int i = 0; i < n; ++i) {
                    if (room[i].back() < minT) {
                        minT = room[i].back();
                        minI = i;
                    }
                }
                room[minI].push_back(meeting[1] - meeting[0] + room[minI].back());
            }
            int ansN = 0, ansIdx;
            for (int i = 0; i < n; ++i) {
                if (room[i].size() > ansN) {
                    ansN = room[i].size();
                    ansIdx = i;
                }
            }
            return ansIdx;
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

写完前三道题时间只剩下十几分钟了，本来想放弃这道题，但是看了一眼题目觉得就是一个很简单的模拟题嘛，踌躇了一会还是开始写，越写越觉得简单，结果11:55提交一次爆long long，改正没有改正完全，12:02通过了，还是有些遗憾。不过没有注意题目的数据范围，这个锅我自己背。

周赛总结

优点

总体思维比较活跃，思维转换速度比较快，实现也还可以。虽然和厉害的人相比还是有差距，但是我觉得已经很不错了，尤其是第二题在没有思路的情况下用记忆化搜索过了真不错。

缺点

还是有些不自信，第四题如果我在第三题做完就全力以赴可能是可以A的，另一个方面是自己忘记去看数据范围了，导致爆long long，改正又忘记后面没有改，自食恶果。

改进方案

多加训练，再接再厉。