LeetCode ---400周赛

题目列表

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;
    }
};

相关推荐

  1. LeetCode401个人题解

    2024-06-09 22:28:04       7 阅读

最近更新

  1. MySQL中的隐式转换(Implicit Conversion)

    2024-06-09 22:28:04       0 阅读
  2. 什么是内存泄漏?如何避免内存泄漏?

    2024-06-09 22:28:04       0 阅读
  3. Web前端级别要求:深入剖析技能层次与发展路径

    2024-06-09 22:28:04       0 阅读
  4. git-本地项目与git连接及上传【快速教程】

    2024-06-09 22:28:04       0 阅读
  5. “先票后款”条款的效力认定

    2024-06-09 22:28:04       0 阅读
  6. 第一章 基本指令

    2024-06-09 22:28:04       0 阅读
  7. 制作手机IOS苹果ipa应用的重签名工具

    2024-06-09 22:28:04       0 阅读

热门阅读

  1. 04-4.1.2 串的存储结构

    2024-06-09 22:28:04       6 阅读
  2. 【react】useEffect 快速上手

    2024-06-09 22:28:04       4 阅读
  3. android-线程池3

    2024-06-09 22:28:04       4 阅读
  4. process to develop linux 5.4

    2024-06-09 22:28:04       5 阅读
  5. 软设之排序算法对比

    2024-06-09 22:28:04       4 阅读
  6. ghidra

    2024-06-09 22:28:04       6 阅读
  7. P11 品牌管理

    2024-06-09 22:28:04       6 阅读
  8. 爬山算法的详细介绍

    2024-06-09 22:28:04       6 阅读
  9. Flutter 常见报错记录

    2024-06-09 22:28:04       5 阅读
  10. 解决更新Android Studio后下载Gradle超时

    2024-06-09 22:28:04       5 阅读