LeetCode周赛309，米哈游赞助的比赛居然不收简历……

语言: CN / TW / HK
时间 2022-10-10 16:15:37

大家好，我是梁唐。

LeetCode系列原本是周一更新的，但由于昨天恰了个饭，因此推迟一天。

LeetCode周赛309由大名鼎鼎的米哈游赞助，米哈游也是近期唯一一个不提供简历直通内推机会的赞助商……

这一场的难度比之前略大一些，很多同学在评论区反应心态崩了……

很遗憾这一场比赛我没有参加（刚好收到密接短信联系社区去了……），我是赛后补的。但即便是在赛后比较轻松的状态下，依然做得不是很顺利，也侧面体现这一场的难度。

好了，我们闲言少叙，来看题吧。

检查相同字母间的距离

给你一个下标从 0 开始的字符串 s ，该字符串仅由小写英文字母组成，s 中的每个字母都 恰好 出现 两次 。另给你一个下标从 0 开始、长度为 26 的的整数数组 distance 。

字母表中的每个字母按从 0 到 25 依次编号（即，'a' -> 0, 'b' -> 1, 'c' -> 2, ... , 'z' -> 25）。

在一个 匀整 字符串中，第 i 个字母的两次出现之间的字母数量是 distance[i] 。如果第 i 个字母没有在 s 中出现，那么 distance[i] 可以 忽略 。

如果 s 是一个 匀整 字符串，返回 true ；否则，返回 false 。

题解

主要的坑点在读题，需要注意如果某个字符串没有出现过，那么它的距离统统视为合法。

```cpp class Solution { public: bool checkDistances(string s, vector& distance) { map mp; for (int i = 0; i < s.length(); i++) { char c = s[i]; if (!mp.count(c)) mp[c] = i; else distance[c-'a'] -= (i - mp[c] - 1); }

    for (int i = 0; i < 26; i++) {
        if (distance[i] != 0 && mp.count('a'+i)) return false;
    }
    return true;
}

}; ```

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

给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意：数轴包含负整数。

题解

表面上看很容易想到搜索或者是动态规划，但实际上这是一道数学题。

由于我们只需要考虑可行解的数量，我们可以强行规定左边的点是起点，右边的点是终点。加上我们 知道了一共需要的步数k，所以我们可以算出向左、向右移动的步数。到这里会发现这其实是一个组合问题，我们假设向左移动lef，向右移动rig。

那么应该满足lef + rig = k,start + rig - lef = end。这是一个很简单的二元一次方程，求解即可。另外还需要注意，rig和lef都是非负整数。如果算出来是负数或者不为整数，说明无解。

求出了lef和rig之后，剩下的就是一个组合问题，我们要求的答案就是$C_k^{rig}$。

这里有一个问题，由于答案可能很大，所以我们需要在计算的过程当中取模。但是组合数的运算会用到除法，但对于取模运算，除法不满足结合律，即$a \bmod p * b \bmod p = ab \bmod p$，但是没有$a \mod p \div b \bmod p \neq \frac a b \bmod p$。

要解决这个问题有两种办法，第一种办法是通过$C_i^j = C_{i-1}^j + C_{i-1}^{j-1}$来推算，第二种办法是求逆元。我们要求$\frac a b \bmod p$的结果，可以转化成乘上$b$关于$a$和$p$的逆元。

这两种方法都可以，我个人用的是逆元法。关于逆元的原理以及计算方法，这里不做过多介绍了，大家感兴趣可以查阅相关资料。

附上代码：

```cpp class Solution { public: typedef long long lint; void Exgcd(lint a,lint b,lint &x,lint &y){ if(!b) x=1,y=0; else Exgcd(b,a%b,y,x), y-=a/b*x; }

int inverse(lint a, lint p){
    lint x, y;
    Exgcd (a,p,x,y);
    x = (x%p+p)%p;
    return x; 
}

int numberOfWays(int st, int ed, int k) {
    int Mod = 1e9 + 7;
    int start = min(st, ed);
    int end = max(st, ed);

    int rig = end - start;
    int lef = k - rig;

    if (lef < 0 || lef % 2) return 0;
    rig += lef / 2;
    lint ret = 1;

    for (int i = 0; i < rig; i++) {
        ret = ret * (k - i) % Mod;
        ret = ret * inverse(i+1, Mod) % Mod;
    }

    return ret;
}

}; ```

最长优雅子数组

给你一个由 正 整数组成的数组 nums 。

如果 nums 的子数组中位于 不同 位置的每对元素按位 与（AND）运算的结果等于 0 ，则称该子数组为 优雅 子数组。

返回 最长 的优雅子数组的长度。

子数组 是数组中的一个 连续 部分。

注意：长度为 1 的子数组始终视作优雅子数组。

题解

这题题意里藏着坑，主要是子数组而非子序列，这两者的意思完全不同。子序列可以不连续，但子数组必须连续。

我们很容易发现，假设我们找到了一个完美子数组，那么这个子数组内的任意两个数的与值为0。转化成二进制，即这若干个数的每一个二进制位最多只有一个1。

有了这个限制条件之后很容易想到two pointers算法，我们维护一段区间内所有二进制位1的个数。如果新增一个数之后会导致某一位的个数大于1，那么从左边进行弹出操作，直到每一个二进制位最多只有一个1为止。

```cpp class Solution { public: // 将整数转化成二进制表示 vector to_bit(int x) { vector ret(33, 0); for (int i = 0; i < 32; i++) { if (x & (1 << i)) ret[i] = 1; } return ret; }

int longestNiceSubarray(vector<int>& nums) {
    int ret = 1;
    int l = 0, st = nums[0];
    int n = nums.size();
    // 存放当前区间内二进制1的数量
    vector<int> bits = to_bit(nums[0]);

    for (int r = 1; r < n; r++) {
        vector<int> cur = to_bit(nums[r]);
        // 标记是否存在某一位的1的数量大于1
        bool flag = false;
        for (int i = 0; i < 32; i++) {
            bits[i] += cur[i];
            if (bits[i] > 1) flag = true;
        }
        while (flag) {
            cur = to_bit(nums[l]);
            flag = false;
            for (int i = 0; i < 32; i++) {
                bits[i] -= cur[i];
                if (bits[i] > 1) flag = true;
            }
            l++;
        }
        ret = max(ret, r - l + 1);
    }
    return ret;
}

}; ```

会议室 III

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

  1. 每场会议都会在未占用且编号 最小 的会议室举办。
  2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
  3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

题解

模拟题，由于会议开始的时间各不相同，我们可以对会议进行排序，从最先开始的会议开始安排。

对于每一个会议，我们要找到最先空出来的会议室，如果有多个空的，我们选择序号最小的。观察一下数据范围，会议最多是1e5个，会议室最多有100个。对于每个会议我们需要遍历一次所有的会议室。那么总的复杂度就是1e7，在可接受的范围内。

当然如果想要优化也可以使用线段树这样的数据结构，可以把会议室的查询降低到logN。但我个人感觉意义不大，大家如果感兴趣可以看看大佬的博客。

要注意会议延续的时间可能会很长，超过int的范围，所以要用int64。

```cpp class Solution { public: int mostBooked(int n, vector>& meetings) { typedef long long lint; vector mst(n, 0), cnt(n, 0);

    const lint MAXI = 0x3f3f3f3f3f3f3f3f;
    sort(meetings.begin(), meetings.end());
    for (auto &vt: meetings) {
        lint sta = vt[0], end = vt[1];
        int choose = -1;
        lint mini = MAXI;
        bool not_exceed = false;
        for (int i = 0; i < n; i++) {
            if (mst[i] <= sta) {
                choose = i;
                not_exceed = true;
                break;
            }
            if (mst[i] < mini) {
                mini = mst[i];
                choose = i;
            }
        }

        if (not_exceed) {
            mst[choose] = end;
        }else {
            mst[choose] += end - sta;
        }

        cnt[choose] ++;
    }

    int mxi = -1, ret = -1;
    for (int i = 0; i < n; i++) {
        if (cnt[i] > mxi) {
            mxi = cnt[i];
            ret = i;
        }
    }
    return ret;
}

}; ```

「」
「」