题目列表
3168. 候诊室中的最少椅子数
3169. 无需开会的工作日
3170. 删除星号以后字典序最小的字符串
3171. 找到按位与最接近 K 的子数组
一、候诊室中的最少椅子数
简单的模拟题，我们可以这样来模拟：当有顾客来时，我们加一把椅子，当有顾客走时，我们减少一把椅子，这样我们就i能动态的获得所有时刻需要的椅子数量，取最大值即可，代码如下
class Solution {
public:
int minimumChairs(string s) {
int ans = 0, cnt = 0;
for(auto e:s){
if(e == 'E') cnt++;
else cnt--;
ans = max(ans, cnt);
}
return ans;
}
};二、无需开会的工作日
这里有两种思路：1、直接算放假天数，2、先算开会天数，再用总数减去上班天数得到放假天数，这两种方法都可以，代码如下
// 方法一：直接算放假天数
class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
int n = meetings.size();
sort(meetings.begin(),meetings.end());
int ans = 0, end = 0;
for(int i = 0; i < n; i++){
if(meetings[i][0]>end) ans += meetings[i][0] - end - 1;
end = max(end, meetings[i][1]);
}
if(end < days) ans += days - end;
return ans;
}
};
// 方法二：先算开会天数，再得出放假天数
class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
int n = meetings.size();
sort(meetings.begin(),meetings.end());
int ans = 0, end = meetings[0][1];
for(int i = 0; i < n;){
int j = i++;
while(i<n && end>=meetings[i][0]-1){
end = max(end, meetings[i][1]);
i++;
}
ans += end - meetings[j][0] + 1;
if(i < n) end = max(end, meetings[i][1]);
}
return days - ans;
}
};三、删除信号以后字典序最小的字符串
题目要求在删除*的同时，删除字典序最小的字符。故这题的关键就在于该如何选择和*一起删除的最小字符？这里先输出结论：删除距离*最近的最小字符得到的字符串最大。为什么呢？
1、假设最小的字符的前后字符都比它大，如cbacbacba中的a，这时，我们无论删除哪一个a都会让字符串的字典序变大，但是删除最右边的a得到的字典序最小(这是由字典序的定义决定的，越靠前的字符的权重越大，因为我们优先比较前面的字符，可以用数字来理解，比如151515，我们肯定选择将最后一个1去掉，这样得到的数字最大，因为它的权重小在十位) => 优先选择靠右的最小字符进行删除。
2、如果有只有一段连续的最小字符呢？如aaaaaaaaab，这时，我们无论删除哪一个a，产生的字符串字典序都相同。如果有多段连续的最小字符呢？如abaabaaab，显然，我们应该优先选择右边的最小字符连续段进行删除操作。
在兼顾1的情况下，我们得出结论：优先选择最靠右的最小字符进行删除，即删除距离*最近的最小字符
代码如下
class Solution {
public:
string clearStars(string s) {
int n = s.size();
vector<vector<int>> pos(26);
for(int i = 0; i < n; i++){
if(isalpha(s[i])) {
pos[s[i]-'a'].emplace_back(i); // 记录字符的位置
}else{
for(auto& v:pos){
if(v.size()){
s[v.back()] = '*'; // 将要删除的最小字符置为*
v.pop_back(); // 从记录中删除
break;
}
}
}
}
s.erase(remove(s.begin(),s.end(),'*'),s.end()); // 删除字符串中的*，O(n)
return s;
}
};四、找到按位与最接近k的子数组
这题考的是&运算的性质：参与&的数字越多，结果越小 --- 具有单调性。在结合题目中要求子数组&的结果，其实就可以用滑动窗口来做，思路如下
假设[ L，R ] 的子数组&结果为res
- 如果res>k，我们让res继续和后面的数进行&，因为res可以变的更小，即可能更加靠近k
- 如果res=k，可以直接返回0
- 如果res<k，由于&的数子越多，res越小，我们需要将左端点向右移，减少区间内的数字，让res变大，才可能更靠近k
所以问题的难点在于如何在移动左端点的同时，维护res？我们可以统计区间中的数字的二进制位0的出现次数，代码如下
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int n = nums.size();
int ans = INT_MAX;
int cnt0[32]{};
int res = -1; // -1的二进制为全1，不影响&结果
for(int l = 0, r = 0; r < n; r++){
// 进窗口
res &= nums[r];
// 统计0的出现次数
for(int i = 0; i < 32; i++)
if((nums[r]>>i&1)==0)
cnt0[i]++;
// 出窗口
while(l < r && res <= k){ // 这里注意 l < r必须要写，因为 当l > r时，res会一直等于-1，会死循环
if(res == k) return 0;
ans = min(abs(k-res), ans); // 注意在<k或者>k的情况下都要更新答案
for(int i = 0; i < 32; i++){
if((nums[l]>>i&1)==0)
if(--cnt0[i]==0)
res |= (1<<i);
}
l++;
}
ans = min(abs(k-res), ans); // 注意在<k或者>k的情况下都要更新答案
}
return ans;
}
};当然这种位运算的题，其实还有另一种通解，简单来说就是暴力枚举所有可能的&结果(可以优化)，代码如下
// O(nlogU) U = max(nums) ，在这里可以认为是O(n)的时间复杂度
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int n = nums.size();
int ans = INT_MAX;
for(int i = 0; i < n; i++){
int x = nums[i];
ans = min(ans, abs(x-k));
// 注意这里的限制条件
// 因为&只能让数字变小，所以一旦[j,i]区间内的数字&结果和原先相同，则nums[i]将无法更新前面的&结果
for(int j = i - 1; j>=0 && (nums[j]&x)!=nums[j]; j--){
nums[j] &= x; // nums[j] 只能变小30次，因为题目范围内的数字二进制最多有30个1
ans = min(ans,abs(nums[j]-k));
}
}
return ans;
}
};
