当前位置：首页 > news >正文

LeetCode ---400周赛

news 来源：原创 2024/9/29 17:25:11

题目列表

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个1ans = min(ans,abs(nums[j]-k));}}return ans;}
};