目录
一，3168. 候诊室中的最少椅子数
二，3169. 无需开会的工作日
三，3170. 删除星号以后字典序最小的字符串
四，3171. 找到按位与最接近 K 的子数组
一，3168. 候诊室中的最少椅子数
本题是一道模拟题，直接使用一个变量存储实时的人数，每次修改之后，与之前的最大值比较，得出答案。
代码如下：
class Solution {
public int minimumChairs(String s) {
int cnt = 0, ans = 0;
for(char ch : s.toCharArray()){
if(ch == 'E'){
cnt++;
}else{
cnt--;
}
ans = Math.max(ans, cnt);
}
return ans;
}
}二，3169. 无需开会的工作日
本题要求没有安排会议的天数，可以正难则反，使用总天数减去工作的天数；也可以直接累加休息的天数。两者意思相同，能理解那种就使用那种。
代码如下：
//正难则反 -> 使用总天数 - 工作天数
class Solution {
public int countDays(int days, int[][] meetings) {
Arrays.sort(meetings,(x,y)->x[0]-y[0]);
int s = 1, e = 0;
for(int[] x : meetings){
if(x[0] > e){
days -= e - s + 1;
s = x[0];
}
e = Math.max(e, x[1]);
}
days -= e - s + 1;
return days;
}
}
//直接算 -> 累加休息的天数
class Solution {
public int countDays(int days, int[][] meetings) {
Arrays.sort(meetings,(x,y)->x[0]-y[0]);
int ans = 0;
int pre = 0;//前一段工作日的最后一天
for(int[] x : meetings){
ans += Math.max(0, x[0] - pre - 1);
pre = Math.max(pre, x[1]);
}
return ans+days-pre;
}
}三，3170. 删除星号以后字典序最小的字符串
本题题意——每次遇到一个' * '字符，就要删去它本身及其前面字典序最小的字符，如果有多个，可以删除其中任意一个，求删除所有 ' * ' 字符后，剩余字符串的最小字符串。
在写本题之前，需要弄清楚一个问题，如果' * '前面有多个相同的最小字符，究竟要删除哪一个，才能使得剩余的字符串最小？例如："aaba*"，我们只有删除最后一个'a'才能使剩余字符串最小。
弄清上述问题后，就可以写代码了，我们可以使用一个堆来统计遇到 '*' 字符前，删除字符的优先级（如果字符不同，按字典序排序；如果字符相同，下标大的排在前面），再使用一个哈希表来统计删除的字符下标，最后再遍历一次字符串s，将保留下来的字符串起来，得到答案。
代码如下：
class Solution {
public String clearStars(String s) {
char[] ch = s.toCharArray();
PriorityQueue<int[]> que = new PriorityQueue<>((x, y) -> {
if(x[0] == y[0]) return y[1] - x[1];//如果字符相同，下标大的排在前面
return x[0] - y[0];//如果字符不同，按字典序排序
});
Set<Integer> set = new HashSet<>();
for(int i=0; i<ch.length; i++){
if(ch[i] != '*'){
que.offer(new int[]{ch[i]-'a', i});
}else{
set.add(que.poll()[1]);//统计删除的字符
set.add(i);
}
}
StringBuilder res = new StringBuilder();
for(int i=0; i<ch.length; i++){
if(!set.contains(i)){
res.append(ch[i]);
}
}
return res.toString();
}
}四，3171. 找到按位与最接近 K 的子数组
1.位运算性质 + 数学
- 该题如果暴力求解，它的时间复杂度为O(n^2)，会超时，但是如果添加一个 if 判断，就可以将它的复杂度降为O(nlogU)，画个图理解一下：
class Solution {
//O(nlogU) U=max(nums)
public int minimumDifference(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
int x = nums[i];
ans = Math.min(ans, Math.abs(k - x));
for(int j=i-1; j>=0; j--){
if((nums[j]&x)==nums[j]) break;
// nums[j] &= x 只会变小，而最多只有32位不一样
// 所以时间复杂度最多就是O(32*n)
nums[j] &= x;
ans = Math.min(ans, Math.abs(k - nums[j]));
}
}
return ans;
}
}2.滑动窗口
- &的性质——&的数越多，&值越小，可以使用滑窗，假设and是【l，r】的&值，如果 and小于 k（再继续&的话，and会更小，abs(k-and)的值就会变大），所以要将 nums[l] 回退，l++。注意：要不断地更新ans的值。
class Solution {
public int minimumDifference(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
int[] cnt = new int[32];
int and = -1;
for(int l=0,r=0; r<nums.length; r++){
and &= nums[r];
for(int i=0; i<32; i++){
cnt[i] += (nums[r]>>i)&1;
}
ans = Math.min(ans, Math.abs(k - and));
while(l <= r && and < k){
for(int i=0; i<32; i++){
cnt[i] -= (nums[l]>>i)&1;
if(cnt[i] == r-l){
and |= (1<<i);
}
}
l++;
ans = Math.min(ans, Math.abs(k - and));
}
}
return ans;
}
}
