leetcode竞赛：20220904周赛

本次题目比较难，体现在中等题比较难。困难题的模拟需要两个堆，思维量也比较大。
日期：20220904
链接：https://leetcode.cn/contest/weekly-contest-309/

题目一 6167. 检查相同字母间的距离

是模拟题，有一定思维量。
比赛代码

class Solution {
public:
    
    bool checkDistances(string s, vector& y) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            int id = s[i] - 'a';
            int ds = y[id];
            ds += 1;
            bool flag = false;
            
            if (i - ds >= 0 && s[i - ds] == s[i]) {
                flag = true;
            }
            if (i + ds < n && s[i + ds] == s[i]) {
                flag = true;
            }
            if (ds == 0) flag = false;
            if (!flag) {
                return false;
            }
        }
        return true;
    }
};
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

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

题目二

比赛时，经验不足还想逆向考虑。实际上看到数据范围，就知道，正向递推一定可做。
比赛代码：数据平移和取模出错了两次，这个不应该，需要反思

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        int a = 1003, b = a + abs(startPos - endPos);
        int p = 1e9 + 7;
        vector> dp(1005, vector(2005));
        dp[0][a] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= 2003; j++) {
                dp[i][j] = dp[i - 1][j - 1] % p  + dp[i - 1][j + 1] % p;
                dp[i][j] %= p;
            }
        }
        return dp[k][b];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其他算法：数学
向净右走m步，向右走r步，向左走l步，那么有公式
r - l = m
r + l = k
计算可得，r = (m + k) / 2
也就是说，从k步中，选r步向右走，也就是计算$C_k^r$
当然，m + k 不可以被2整除以及k < m时，都无解。
计算组合数：https://www.cnblogs.com/Tshaxz/p/15193996.html

1. 杨辉三角递推
2. 求逆元
3. 卢卡斯定理
4. 高精度

杨辉三角打标求组合数。
const int N = 1005, MOD = 1e9 + 7;
int C[N][N];
class Solution {
public:
    void init(int n) {
        memset(C, 0, sizeof C);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (!j) C[i][j] = 1;
                else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
    }
    int numberOfWays(int startPos, int endPos, int k) {
        init(k);
        int res = 0;
        for (int i = 0; i <= k; i++) {
            int j = k - i;
            if (startPos + i - j != endPos) continue;
            cout << k << i << C[k][i] << endl;
            res = (res + C[k][i]) % MOD;
        }
        return res;
    }
};
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

题目三

比赛时，使用了位运算进行优化。实际上不需要。
双指针算法不够熟练，代码写的比较丑。
多插一句：这里为什么可以用双指针?因为两个指针只能往右走。右指针向右的时候，如果左指针可以往左走，那么，右指针在原来位置的时候，左指针就能够在左边的位置。所以左指针位置就是错的，矛盾了。

class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int n = nums.size();
        vector dp(n, 1);
        int cur = nums[0], res = 1;
        for (int i = 1, j = 0; i < n; i++) {
            if (cur & nums[i]) {  // 这里应该直接替换成循环
                res = max(res, i - j);
                while (cur & nums[i] && j < i) {
                    cur &= ~nums[j];
                    j++;
                }
                cur |= nums[i];
            } else {
                cur|= nums[i];
                res = max(res, i - j + 1);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

赛后优化

class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int n = nums.size();
        vector dp(n, 1);
        int cur = nums[0], res = 1;
        for (int i = 1, j = 0; i < n; i++) {
            while (cur & nums[i]) {
                cur &= ~nums[j];
                j++;
            }
            cur |= nums[i];
            res = max(res, i - j + 1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

双指针

class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int res = 0, n = nums.size();
        int cnt = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && !(cnt & nums[j])) {
                cnt |= nums[j++];
            }
            res = max(res, j - i);
            cnt &= ~nums[i];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第四题：6170. 会议室 III

比赛时没做出来，难点在于数据结构的选择与维护。
这个题要用堆来找到可用的，最小编号的会议室。
要用堆来维护哪些会议室当前可用。当没有可用的时候，需要维护哪个会议室最先使用完。
得想清楚这里有两个要维护的东西，需要两个堆来维护
贴一个

#define x first
#define y second
typedef long long LL;
typedef pair PIL;

class Solution {
public:
    int mostBooked(int n, vector>& meetings) {
        int m = meetings.size();
        priority_queue, greater> heap;  // 维护当前可用的会议室编号
        priority_queue, greater> rooms; // 维护使用状态的 最早结束 的会议室
        for (int i = 0; i < n; i ++ ) heap.push(i);

        sort(meetings.begin(), meetings.end());
        vector cnt(n);
        for (auto& p: meetings) {
            while (rooms.size() && rooms.top().x <= p[0]) { // 把当前结束会议的会议室空出来
                heap.push(rooms.top().y);
                rooms.pop();
            }
            if (heap.size()) { // 如果有空的会议室，选最小编号的会议室开始开会
                int t = heap.top();
                heap.pop();
                cnt[t] ++ ;
                rooms.push({p[1], t});
            } else { // 没有空的会议室，选最早结束会议的会议室，更新其结束时间。
                auto t = rooms.top();
                rooms.pop();
                cnt[t.y] ++ ;
                rooms.push({t.x + p[1] - p[0], t.y});
            }
        }

        int res = 0;
        for (int i = 1; i < n; i ++ )
            if (cnt[i] > cnt[res])
                res = i;
        return res;
    }
};

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
39
40
41

第二次写

typedef long long LL;
typedef pair PLI;
class Solution {
public:
    int mostBooked(int n, vector>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue, greater> qid;
        priority_queue, greater> qet;
        for (int i = 0; i < n; i++) qid.push(i);
        int res = -1;
        vector cnts(n);
        for (auto& p : meetings) {
            while (qet.size() && qet.top().first <= (LL)p[0]) {
                qid.push(qet.top().second);
                qet.pop();
            }
            int x = -1;
            if (!qid.empty()) {
                x = qid.top();
                qid.pop();
                qet.push({p[1], x});
            } else {
                auto m = qet.top();
                x = m.second;
                qet.pop();
                m.first += p[1] - p[0];
                qet.push(m);
            }
            // cout << x << endl;
            cnts[x]++;
            if (res == -1 || cnts[x] > cnts[res] || (x < res && cnts[x] == cnts[res])) res = x;
        }
        return res;
    }
};
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