type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 20, 2024 05:32 PM
😀
LeetCode第400场周赛题解
竞赛 - 力扣 (LeetCode)
备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。
竞赛 - 力扣 (LeetCode)
https://leetcode.cn/contest/weekly-contest-400/
竞赛 - 力扣 (LeetCode)

📝 主旨内容

候诊室中的最少椅子数(模拟)

给你一个字符串 s，模拟每秒钟的事件 i：
  • 如果 s[i] == 'E'，表示有一位顾客进入候诊室并占用一把椅子。
  • 如果 s[i] == 'L'，表示有一位顾客离开候诊室，从而释放一把椅子。
返回保证每位进入候诊室的顾客都能有椅子坐的 最少 椅子数，假设候诊室最初是 空的 。
示例 1：
输入：s = "EEEEEEE"
输出：7
解释：
每秒后都有一个顾客进入候诊室，没有人离开。因此，至少需要 7 把椅子。
示例 2：
输入：s = "ELELEEL"
输出：2
解释：
假设候诊室里有 2 把椅子。下表显示了每秒钟等候室的状态。
秒
事件
候诊室的人数
可用的椅子数
0
Enter
1
1
1
Leave
0
2
2
Enter
1
1
3
Leave
0
2
4
Enter
1
1
5
Enter
2
0
6
Leave
1
1
示例 3：
输入：s = "ELEELEELLL"
输出：3
解释：
假设候诊室里有 3 把椅子。下表显示了每秒钟等候室的状态。
秒
事件
候诊室的人数
可用的椅子数
0
Enter
1
2
1
Leave
0
3
2
Enter
1
2
3
Enter
2
1
4
Leave
1
2
5
Enter
2
1
6
Enter
3
0
7
Leave
2
1
8
Leave
1
2
9
Leave
0
3
提示：
  • 1 <= s.length <= 50
  • s 仅由字母 'E' 和 'L' 组成。
  • s 表示一个有效的进出序列。
💡
签到题，答案是同时占用的椅子的最大数量，直接模拟即可

无需开会的工作日(区间合并)

给你一个正整数 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 <= 10^9
  • 1 <= meetings.length <= 10^5
  • meetings[i].length == 2
  • 1 <= meetings[i][0] <= meetings[i][1] <= days
💡
区间合并模板题，总天数-所有区间的并集就是答案

删除星号以后字典序最小的字符串(贪心)

给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
  • 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '*' 字符以后，剩余字符连接而成的
字典序最小
的字符串。
示例 1：
输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
示例 2：
输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。
提示：
  • 1 <= s.length <= 10^5
  • s 只含有小写英文字母和 '*' 字符。
  • 输入保证操作可以删除所有的 '*' 字符。
💡
不难分析出，每次删除时对相同字母需要删除更靠后的才能最终得到字典序最小的字符串
💡
用优先队列去维护非*字符串，首先按照字典序升序，字典序相同再按位置逆序排列

找到按位与最接近 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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
💡
首先明确，按位与操作是不可能使得数变大的，也就是两个数按位与的操作会小于等于原来的两个数，大部分情况是越来越小的
💡
换而言之，区间越长得到的数就越小，最小到0，当到0时再扩展区间就显得没必要了，也就是说在按位与中会产生多个重复值，去重后复杂度就会降到log级别(每次最少改变一位二进制数)

🤗 总结归纳

第二题区间合并，太急了都忘记怎么写了
第三题本来以为写不出，就随便交了一发超时的，稍微想了一下发现还是可行的
第四题只能眼睁睁地看着自己的排名掉了
notion image
上小分只能说，没掉就好

📎 参考文章

 
 
相关文章
2024年春招/实习笔试题解合集
AcWing第150场周赛题解
腾讯2024后台开发实习笔试
华为春招实习笔试题解(0417)
AcWing第152场周赛题解
快手游戏春招笔试题-开发B卷题解
AcWing第155场周赛题解MVTec 3D-AD数据集预处理的意义
Loading...