欢迎大家加QQ群：623375442，可以方便群里面交流。
100307. Minimum Number of Chairs in a Waiting Room
给你一个字符串 s，模拟每秒钟的事件 i：
- 如果 s[i] == 'E'，表示有一位顾客进入候诊室并占用一把椅子。
- 如果 s[i] == 'L'，表示有一位顾客离开候诊室，从而释放一把椅子。
返回保证每位进入候诊室的顾客都能有椅子坐的 最少 椅子数，假设候诊室最初是 空的 。
测试样例：
输入：s = "EEEEEEE"
输出：7
解释：每秒后都有一个顾客进入候诊室，没有人离开。因此，至少需要 7 把椅子。
解答：遍历数组，记一下最大值。
class Solution {
public int minimumChairs(String s) {
int max = 0, count = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == 'E') {
++count;
} else if (s.charAt(i) == 'L') {
--count;
}
max = Math.max(max, count);
}
return max;
}
}100311. Count Days Without Meetings
给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。
返回员工可工作且没有安排会议的天数。
注意：会议时间可能会有重叠。
测试样例：
输入：days = 10, meetings = [[5,7],[1,3],[9,10]]
输出：2
解释：第 4 天和第 8 天没有安排会议。
解答：计算一下前缀和。但是days的范围非常大，不能暴力计算。把meetings中所有出现的节点排序一下。meetings[i][0]代表某个位置+1，meeting[i][1]代表(meetings[i][1] + 1) -1。然后遍历排序完毕的meetings数组，计算一下前缀和。前缀和为0的区间代表没有会议。
class Solution {
public int countDays(int days, int[][] meetings) {
// 偷懒，用了红黑树排序。
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] m : meetings) {
map.put(m[0], map.getOrDefault(m[0], 0) + 1);
map.put(m[1] + 1, map.getOrDefault(m[1] + 1, 0) - 1);
}
int res = 0;
int lastTime = 1, meetingCount = 0;
for (Map.Entry<Integer, Integer> kv : map.entrySet()) {
// 计算前缀和
int nextMeetingCount = meetingCount + kv.getValue();
// 前缀和为0代表没有会议，更新没有会议的区间
if (meetingCount == 0) {
res += kv.getKey() - lastTime;
}
lastTime = kv.getKey();
meetingCount = nextMeetingCount;
}
if (meetingCount == 0) {
res += days + 1 - lastTime;
}
return res;
}
}100322. Lexicographically Minimum String After Removing Stars
给你一个字符串 s 。它可能包含任意数量的 '' 字符。你的任务是删除所有的 '' 字符。
当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
- 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
测试样例：
输入：s = "aaba*"
输出："aab"
解释：删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
解答：将所有非'*'字符串用栈记录下来，每次碰到'*'之后，将最小字符的最大位置出栈（出栈代表删除该字符）。
class Solution {
public String clearStars(String s) {
int len = s.length();
boolean[] isAdd = new boolean[len];
Stack<Integer>[] stacks = new Stack[26];
for (int i = 0; i < 26; ++i) {
stacks[i] = new Stack<>();
}
for (int i = 0; i < len; ++i) {
isAdd[i] = true;
if (s.charAt(i) == '*') {
isAdd[i] = false;
// 最小字符出栈
for (int j = 0; j < 26; ++j) {
if (!stacks[j].isEmpty()) {
isAdd[stacks[j].pop()] = false;
break;
}
}
} else {
stacks[s.charAt(i) - 'a'].push(i);
}
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < len; ++i) {
if (isAdd[i]) {
res.append(s.charAt(i));
}
}
return res.toString();
}
}100315. Find Subarray With Bitwise AND Closest to K
给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位与运算 AND 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] AND nums[l + 1] ... AND nums[r])| 最小。
请你返回 最小 的绝对差值。
子数组是数组中连续的 非空 元素序列。
测试样例：
输入：nums = [1,2,4,5], k = 3
输出：1
解释：子数组 nums[2..3] 的按位 AND 运算值为 4 ，得到最小差值 |3 - 4| = 1 。
解答：经典双指针。与运算符牵涉的数字越多，结果是单调递减的。利用双指针寻找第一个AND区间大于k的范围（可能寻找不到，注意不要指针越界）。
class Solution {
public int minimumDifference(int[] nums, int k) {
int[] arr = new int[30];
int res = Integer.MAX_VALUE;
int st = 0, ed = 0;
while (ed < nums.length) {
refresh(arr, nums[ed], 1);
int add = countNum(arr, ed - st + 1);
res = Math.min(res, Math.abs(k - add));
while (st <= ed && add < k) {
refresh(arr, nums[st++], -1);
add = countNum(arr, ed - st + 1);
res = Math.min(res, Math.abs(k - add));
}
++ed;
}
return res;
}
private void refresh(int[] arr, int num, int diff) {
for (int i = 0; i < 30; ++i) {
if (isMark(num, i)) {
arr[i] += diff;
}
}
}
private int countNum(int[] arr, int len) {
int res = 0;
for (int i = 0; i < 30; ++i) {
if (arr[i] == len) {
res += (1 << i);
}
}
return res;
}
private boolean isMark(int num, int offset) {
int tmp = (num >> offset) & 1;
return tmp == 1;
}
}