第 309 场周赛

A 检查相同字母间的距离

模拟，用哈希表记录每个字符第一次出现的位置，再次出现时判断相隔长度是否符合 distance 的要求。

C++Python

class Solution {
public:
    bool checkDistances(string s, vector<int>& distance) {
        unordered_map<int, int> mp;
        for(int i = 0; i < s.size(); i++) {
            int c = s[i] - 'a';
            if(!mp.count(c)) mp[c] = i;
            else {
                if(i - mp[c] - 1 != distance[c]) return false;
            }
        }
        return true;
    }
};

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        last_emerge = {}
        for i in range(len(s)):
            c = ord(s[i]) - ord('a')
            if c in last_emerge:
                if distance[c] != i - last_emerge[c] - 1:
                    return False
            else:
                last_emerge[c] = i
        return True

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

动态规划，\(d[t][i]\) 表示时刻 \(t\) 走到位置 \(i\) 的方法数，注意到 \(i\) 的范围可能是 \(-1000 \sim 2000\)，为了让普通数组可以访问，将整体坐标向右偏移 \(BASE = 1000\) 个单位。

如此，每个位置转移：\(d[t][i] = d[t - 1][i - 1] + d[t - 1][i + 1]\)，使用滚动数组可以进一步优化空间复杂度。

时间复杂度为 \(O(3000k)\)。

C++Python

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        const int MOD = 1E9 + 7;
        const int BASE = 1000, N = 3001;
        vector<int> d(N);
        d[startPos + BASE] = 1;
        auto f = d;
        for(int i = 0; i < k; i ++) {
            for(int j = 0; j < N; j++) {
                f[j] = 0;
                if(j > 0) f[j] += d[j - 1];
                if(j + 1 < N) f[j] += d[j + 1];
                f[j] %= MOD;
            }
            d = f;
        }
        return d[endPos + BASE];
    }
};

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD = int(1E9 + 7)
        BASE, N = 1000, 3001
        d = [0] * N
        f = [0] * N
        d[startPos + BASE] = 1

        for i in range(k):
            for j in range(N):
                f[j] = 0
                if j > 0: f[j] += d[j - 1]
                if j + 1 < N: f[j] += d[j + 1]
                f[j] %= MOD
            d = [x for x in f]
        return d[endPos + BASE]

DP 的另外一种实现方式是记忆化搜索，Python 可以比较方便的实现：

Python 记忆化搜索

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD = int(1E9 + 7)
        @cache
        def get(pos: int, rest: int) -> int:
            if rest == 0: return pos == endPos
            if abs(pos - endPos) > rest: return 0
            return (get(pos + 1, rest - 1) + get(pos - 1, rest - 1)) % MOD

        return get(startPos, k)

C 最长优雅子数组

注意到数据范围 \(1\le nums[i] \le 10^9\)，所以最多只会有 31 个数字。根据鸽巢原理（抽屉原理），当子数组包含超过 31 个元素时，一定可以找到两个元素按位与结果大于 0。

所以，直接暴力遍历即可。

C++Python

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int res = 1;
        for(int i = 0; i < nums.size(); i++) {
            int mask = nums[i];
            int j = i - 1;
            while(j >= 0 && (mask & nums[j]) == 0) {
                mask |= nums[j];
                j --;
            }
            res = max(res, i - j);
        }
        return res;
    }
};

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        res = 1
        for i in range(len(nums)):
            mask = 0
            j = i
            while j >= 0 and (mask & nums[j]) == 0:
                mask |= nums[j]
                j -= 1
            res = max(res, i - j)
        return res

D 会议室 III

首先需要对每场会议按照 start 排序，然后优先考虑 start 更小的会议去安排会议室。

首先用一个优先队列去维护每个会议室，记录的信息包括会议室下一次变为空闲的时刻以及会议室 ID。每次优先取出最先变为空闲的会议室，如果有多个这样的会议室，则优先取出 ID 更小的。

注意到，如果对于当前会议 \(i\)，在 \(start_i\) 之前变为空闲的会议室可能有多个。例如两个会议室分别在 \(t_u, t_v\) 时刻变为空闲， \(t_u \lt t_v \le start_i\)，而 \(u \gt v\)，按照题意我们应当选择 \(v\)。

因此，还需要一个优先队列，及时的将当前变为空闲的会议室全部加入到该队列中，然后优先取出会议室 ID 最小的一个。

时间复杂度为 \(O(m\log n)\), 其中 \(m\) 是会议个数，\(n\) 是会议室个数。

C++Python

class Solution {
public:
    using ll = long long;
    using PLI = pair<ll, int>;
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue<PLI, vector<PLI>, greater<PLI>> q;
        priority_queue<int, vector<int>, greater<int>> q2;
        for(int i = 0; i < n; i++) {
            q2.push(i);
        }

        vector<int> res(n);

        for(int i = 0; i < meetings.size(); i++) {
            int st = meetings[i][0], ed = meetings[i][1];
            while(q.size() && q.top().first <= st) {
                q2.push(q.top().second); q.pop();
            }

            if(q2.size()) {
                int idx = q2.top(); q2.pop();
                q.push(make_pair(ed, idx));
                res[idx] ++;
            } else {
                auto [t, idx] = q.top(); q.pop();
                q.push(make_pair(t + ed - st, idx));
                res[idx] ++;
            }
        }
        int max_time = 0, idx = 0;
        for(int i = 0; i < n; i++) {
            if(res[i] > max_time) {
                max_time = res[i];
                idx = i;
            }
        }
        return idx;
    }
};

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        q = []
        q2 = list(range(n))
        res = Counter()

        for st, ed in meetings:
            while q and q[0][0] <= st:
                time, idx = heappop(q)
                heappush(q2, idx)
            if q2:
                idx = heappop(q2)
                res[idx] += 1
                heappush(q, [ed, idx])
            else:
                time, idx = heappop(q)
                res[idx] += 1
                heappush(q, [time + ed - st, idx])

        max_time, idx = 0, 0
        for i in range(n):
            if max_time < res[i]:
                max_time = res[i]
                idx = i
        return idx

本文访问次