leetcode contest 309

今天周赛的题目质量还算蛮高，都不是特别水的题目，还是非常好的题目

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

题目

给你一个下标从 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 。

示例 1：

输入：s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：true
解释：
- 'a' 在下标 0 和下标 2 处出现，所以满足 distance[0] = 1 。
- 'b' 在下标 1 和下标 5 处出现，所以满足 distance[1] = 3 。
- 'c' 在下标 3 和下标 4 处出现，所以满足 distance[2] = 0 。
注意 distance[3] = 5 ，但是由于 'd' 没有在 s 中出现，可以忽略。
因为 s 是一个匀整字符串，返回 true 。

示例 2：

输入：s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
输出：false
解释：
- 'a' 在下标 0 和 1 处出现，所以两次出现之间的字母数量为 0 。
但是 distance[0] = 1 ，s 不是一个匀整字符串。

提示：

• 2 <= s.length <= 52
• s 仅由小写英文字母组成
• s 中的每个字母恰好出现两次
• distance.length == 26
• 0 <= distance[i] <= 50

地址

https://leetcode.cn/contest/weekly-contest-309/problems/check-distances-between-same-letters/

题意

直接遍历

思路

1. 我们可以直接遍历该数组即可， 直接找到相同字母之间的距离是否与数组 $distance$ 相同。
2. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度。
• 空间复杂度：$O(1)$。

代码

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

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

题目

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

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

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

注意：数轴包含负整数。

示例 1：

输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。

示例 2：

输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。

提示：

• 1 <= startPos, endPos, k <= 1000

地址

https://leetcode.cn/contest/weekly-contest-309/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/

题意

动态规划 + 数学方法

思路

1. 典型的动态规划解题思路即可。设 $dp[i][j]$ 表示第 $i$ 步在位置 $j$ 的方法数，则可以知道递推公式为:
   $$
   dp[i][j] = dp[i-1][j-1] + dp[i-1][j + 1]。
   $$
   最终返回的结果即为 $dp[k][k + abs(endPos - startPos)]$。

• 我们可以很容易的分析出来当 $abs(endPos - startPos) > k$ 时则无法达到目的地。

2. 数学方法：总共走了 $k$ 步，我们设从 $start \rightarrow end$ 为正方向，反向为负方向 $end \rightarrow start$，假设我们往正方向走了 $x$ 步，往负方向走了 $k - x$ 步，最终到达某个坐标，根据排列组合可以知道可能的方案数位 $C_k^x$，根据题意可以知道 $x - (k - x) = end - start$，此时可以知道 $x = \dfrac{k + end -start}{2}$，此时我们只需要求出 $C_k^x$ 即可，根据排列组合公式可知 $C_k^x = C_{k-1}^{x-1} + C_{k-1}^{x}$，如果需要优化则可以利用乘法逆元进一步进行优化，可以在 $O(k)$ 的时间复杂度内求出结果。
3. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(k^2)$，$k$ 表示给定的元素。
• 空间复杂度：空间复杂度为 $O(k)$。

代码

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        long long mod = 1e9 + 7;
        int x = abs(startPos - endPos);
        vector<vector<long long>> dp(k + 1, vector<long long>(2*k + 1, 0));
        dp[0][k] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j <= 2 * k; j++) {
                if (dp[i-1][j] != 0) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i-1][j]) % mod;
                    dp[i][j - 1] = (dp[i][j - 1] + dp[i-1][j]) % mod;
                }
            }
        }
        if (x > k) {
            return 0;
        }
        return dp[k][k+x];
    }
};

• 数学解法：

  class Solution { public: int numberOfWays(int startPos, int endPos, int k) { int x = abs(endPos - startPos) + k; if (x % 2 == 1 || x > 2 * k) { return 0; } x = x / 2; vector<vector<int>> comb(k + 1, vector<int>(x + 1)); for (int i = 0; i <= x; i++) { comb[i][i] = 1; comb[i][0] = 1; } long long mod = 1e9 + 7; for (int i = 1; i <= k; i++) { for (int j = 1; j <= x && j < i; j++) { comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod; } } return comb[k][x]; } };

6169. 最长优雅子数组

题目

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

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

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

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

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

示例 1：

输入：nums = [1,3,8,48,10]
输出：3
解释：最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：
- 3 AND 8 = 0
- 3 AND 48 = 0
- 8 AND 48 = 0
可以证明不存在更长的优雅子数组，所以返回 3 。

示例 2：

输入：nums = [3,1,5,11,13]
输出：1
解释：最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-309/problems/longest-nice-subarray/

题意

暴力判断

思路

1. 根据题目可以知道由于 int 整形最多只有 $32$ 个数组，因此我们直接检测连续的区间是否满足相与的情况即可，此时我们可以保存当前组中每个元素相或的结果 $x$，如果当前元素与 $x$ 相与的结果为 $0$，则表示 $x$ 与当前组中的任意元素相与都等于 $0$。
2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n \times \log(\max(nums)))$，$n$ 为数组的长度。
• 空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int curr = nums[i];
            int now = 1;
            for (int j = i + 1; j < n && (nums[j] & curr) == 0; j++) {
                curr |= nums[j];
                now++;
            }
            ans = max(ans, now);
        }
        return ans;
    }
};

6170. 会议室 III

题目

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

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

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

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

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

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

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。 

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。 

提示：

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• starti 的所有值 互不相同

`

地址

https://leetcode.cn/contest/weekly-contest-309/problems/meeting-rooms-iii/

题意

堆

思路

1. 我们采用优先队列来讲所有的房间都入队列，且每次队列中优先弹出结束时间最早的房间，相同的结束时间条件下，会弹出编号最小的房间。

• 首先按照会议开始时间的先后进行排序，我们每次从起始时间最早的会议开始检测
• 设当前队列中弹出的房间的结束时间为 $x$，则我们将所有结束时间小于 $x$ 的房间全部弹出，并以当前会议的起始时间为结束时间，再次将房间压入队列中；
• 队列中每次弹出的元素即为满足条件下，结束时间最早且编号最小的房间；
• 如果 $x$ 小于等于当前的结束

2. 复杂度分析：

• 时间复杂度：$O(m \times \log n)$，其中 $m$ 表示数组的长度，$n$ 为房间数目。
• 空间复杂度：$(n)$，$n$ 为房间数目。

代码

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        int m = meetings.size();
        sort(meetings.begin(), meetings.end());
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        for (int i = 0; i < n; i++) {
            pq.emplace(0, i);
        }
        vector<int> cnt(n);
        for (auto v : meetings) {
            int start = v[0], end = v[1];
            while (pq.top().first < start) {
                int x = pq.top().second;
                pq.pop();
                pq.emplace(start, x);
            }
            auto [time, idx] = pq.top();
            pq.pop();
            cnt[idx]++;
            if (time <= start) {
                pq.emplace(end, idx);
            } else {
                pq.emplace(time + end - start, idx);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[ans]) {
                ans = i;
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿