leetcode weekly contest 400

t4 又是经典的双指针问题，比较模板化的题目了。

100307. 候诊室中的最少椅子数

给你一个字符串 s，模拟每秒钟的事件 i：

• 如果 s[i] == 'E'，表示有一位顾客进入候诊室并占用一把椅子。
• 如果 s[i] == 'L'，表示有一位顾客离开候诊室，从而释放一把椅子。

返回保证每位进入候诊室的顾客都能有椅子坐的 最少 椅子数，假设候诊室最初是 空的 。

示例 1：

输入：s = “EEEEEEE”

输出：7

解释：

每秒后都有一个顾客进入候诊室，没有人离开。因此，至少需要 7 把椅子。

示例 2：

输入：s = “ELELEEL”

输出：2

解释：

假设候诊室里有 2 把椅子。下表显示了每秒钟等候室的状态。

示例 3：

输入：s = “ELEELEELLL”

输出：3

解释：

假设候诊室里有 3 把椅子。下表显示了每秒钟等候室的状态。

提示：

• 1 <= s.length <= 50
• s 仅由字母 'E' 和 'L' 组成。
• s 表示一个有效的进出序列。

地址

https://leetcode.cn/contest/weekly-contest-400/problems/minimum-number-of-chairs-in-a-waiting-room/

题意

直接枚举

思路

1. 统计当前字符串中最大的 E 的统计数目即可，与多任务 CPU 类似。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$, 其中 $n$ 表示数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def minimumChairs(self, s: str) -> int:
        res, cur = 0, 0
        for c in s:
            if c == 'E':
                cur += 1
            else:
                cur -= 1
            res = max(res, cur)
        return res

impl Solution {
    pub fn minimum_chairs(s: String) -> i32 {
        let mut res = 0;
        let mut cur = 0;
        for ch in s.chars() {
            if ch == 'E' {
                cur += 1;
            } else {
                cur -= 1;
            }
            res = res.max(cur);
        }
        res
    }
}

100311. 无需开会的工作日

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]

输出：2

解释：

第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]

输出：1

解释：

第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]

输出：0

解释：

所有工作日都安排了会议。

提示：

• 1 <= days <= 109
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

地址

https://leetcode.cn/contest/weekly-contest-399/problems/string-compression-iii/

题意

排序

思路

1. 按照会议开始时间排序后，统计相邻两次会议之间的空闲时间即可，如果最后的时间小于等于 $days$ , 此时还需要统计空闲时间。
2. 复杂度分析：

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

代码

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        start, res = 1, 0
        for l, r in meetings:
            if l > start:
                res += max(0, min(days, l - 1) - start + 1)
            start = max(start, r + 1)
        if start <= days:
            res += days - start + 1
        return res

impl Solution {
    pub fn count_days(days: i32, meetings: Vec<Vec<i32>>) -> i32 {
        let mut meetings = meetings;
        meetings.sort();
        let mut start = 1;
        let mut res = 0;
        for vec in meetings.iter() {
            let l = vec[0];
            let r = vec[1];
            if l > start {
                res += std::cmp::max(0, std::cmp::min(days, l - 1) - start + 1);
            }
            start = std::cmp::max(start, r + 1);
        }
        if start <= days {
            res += days - start + 1;
        }
        res
    }
}

100322. 删除星号以后字典序最小的字符串

给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

• 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。

示例 1：

输入：s = “aaba*”

输出：“aab”

解释：

删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = “abc”

输出：“abc”

解释：

字符串中没有 '*' 字符。

提示：

• 1 <= s.length <= 105
• s 只含有小写英文字母和 '*' 字符。
• 输入保证操作可以删除所有的 '*' 字符。

地址

https://leetcode.cn/contest/weekly-contest-400/problems/lexicographically-minimum-string-after-removing-stars/

题意

贪心

思路

1. 由于每次遇到 * 时需要删除左侧字典序最小的字符，根据贪心原则我们应当删除排在最后的字典序最小的字符，按照该贪心思路模拟即可，感觉是个简单题目了。
2. 复杂度：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度；
• 空间复杂度：$O(n)$，其中 $n$ 表示给定字符串的长度；

代码

class Solution:
    def clearStars(self, s: str) -> str:
        n = len(s)
        cnt = [[] for _ in range(26)]
        flag = [0] * n
        for i, ch in enumerate(s):
            if s[i] != '*':
                cnt[ord(s[i]) - ord('a')].append(i)
            else:
                for j in range(26):
                    if len(cnt[j]) > 0:
                        flag[cnt[j][-1]] = 1
                        cnt[j].pop()
                        break

        res = ""
        for i, ch in enumerate(s):
            if s[i] != '*' and flag[i] == 0:
                res += s[i]
        return res

100315. 找到按位与最接近 K 的子数组

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位与运算 AND 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] AND nums[l + 1] ... AND nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组是数组中连续的 非空 元素序列。

示例 1：

输入：nums = [1,2,4,5], k = 3

输出：1

解释：

子数组 nums[2..3] 的按位 AND 运算值为 4 ，得到最小差值 |3 - 4| = 1 。

示例 2：

输入：nums = [1,2,1,2], k = 2

输出：0

解释：

子数组 nums[1..1] 的按位 AND 运算值为 2 ，得到最小差值 |2 - 2| = 0 。

示例 3：

输入：nums = [1], k = 10

输出：9

解释：

只有一个子数组，按位 AND 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-400/problems/find-subarray-with-bitwise-and-closest-to-k/

题意

双指针或者二分查找

思路

1. 我们知道题目的关键在于 $a \And b \le a$，任何一个数与另一个数与操作后都小于原来的数，因此知道这个性质后，我们枚举子树的右端点 $r$，此时通过二分查找找到最接近 $k$ 的左端点 $l$，此时二分查找最直接的是我们可以利用线段树或者数位前缀和统计计算均可，在此不再描述该解法；

2. 双指针的解法也比较简单，每次固定右端点 $r$，此时计算当前区间 $[l,r]$ 中进行与操作的结果 $s(l,r)$，如果 $s(l,r) < k$ 时，此时按照贪心原则我们应该向右移动左边界 $l$ 直到 $s(l,r) \ge k$ 为止，每次移动时我们利用数位的前缀和统计计算 $s(l,r)$ 即可，整体运算比较简单，每次统计前缀中所有含有 $0$ 与 $1$ 的数目，如果当前区间中 $0$ 的数目为 $0$, 且 $1$ 的数目大于 $0$ ，则当前位应该为 $1$;

3. 复杂度分析：

• 时间复杂度：$O(n \times \log^2 U)$，其中 $n$ 表示给定查询的数组的长度， $U$ 表示给定查询中元素的最大数目；
• 空间复杂度：$O(1ogU)$， $U$ 表示给定查询中元素的最大数目；

代码

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        cnt0 = [0] * 32
        cnt1 = [1] * 32
        
        def add(x: int):
            for i in range(32):
                if x & (1 << i):
                    cnt1[i] += 1
                else:
                    cnt0[i] += 1
        
        def remove(x: int):
            for i in range(32):
                if x & (1 << i):
                    cnt1[i] -= 1
                else:
                    cnt0[i] -= 1
        
        def get():
            res = 0
            for i in range(32):
                if cnt0[i] == 0 and cnt1[i] > 0:
                    res |= (1 << i)
            return res
        
        res = inf
        j = 0
        for i, x in enumerate(nums):
            add(x)
            while j < i and get() < k:
                res = min(res, abs(get() - k))
                remove(nums[j])
                j += 1
            res = min(res, abs(get() - k))
        return res

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者