LeetCode：第 400 场周赛

总结

最值得做的还是最后一题，最后一题使用集合论的思想非常的有意思，值得总结。

Q1：3168. 候诊室中的最少椅子数

题目传送门：3168. 候诊室中的最少椅子数 - 力扣（LeetCode）

周常签到题目，遍历一遍即可。

最后实现代码如下：

class Solution {
public:
    int minimumChairs(string s) {
        int ans = 0, tmp = 0;
        for (char &c : s){
            if (c == 'E') tmp++;
            else tmp--;
            ans = max(ans, tmp);
        }
        return ans;
    }
};

Q2：3169. 无需开会的工作日

题目传送门：3169. 无需开会的工作日 - 力扣（LeetCode）

对区间进行一个从小到大的排序，然后合并区间的途中计算区间覆盖的天数，最后使用总天数-开会天数得到最终的空闲天数。

最后实现代码如下：

class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        int n = meetings.size();
        sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b){
            if (a[0]!=b[0]) return a[0] < b[0];
            return a[1] < b[1];
        });
        int meetdays = 0;
        int start = meetings[0][0], end = meetings[0][1];
        for (int i=1;i<n;++i) {
            if (meetings[i][0] >= start && meetings[i][0] <= end) {
                end = max(meetings[i][1], end);
            } else {
                meetdays += (end - start + 1);
                start = meetings[i][0];
                end   = meetings[i][1];
            }
        }
        meetdays += (end-start + 1);
        return days - meetdays;
    }
};

Q3：3170. 删除星号以后字典序最小的字符串

题目传送门：3170. 删除星号以后字典序最小的字符串 - 力扣（LeetCode）

哈希表，使用一张哈希表存储每种字符（26个）出现的位置，遍历字符串，发现*时，从小到大遍历哈希表，从哈希表中删除最小字符最后出现的位置即可。

最后实现代码如下：

class Solution {
public:
    string clearStars(string s) {
        int n = s.size();
        vector<bool> vis(100003,true);
        vector<vector<int>> mp(26);
        for (int i=0; i<n; ++i) {
            char c = s[i];
            if (c != '*') mp[c-'a'].push_back(i);
            else {
                vis[i] = false;
                for (auto &loc : mp) {
                    if (loc.size()) {
                        int nn = loc.size();
                        vis[loc[nn-1]] = false;
                        loc.pop_back();
                        break;
                    }
                }
            }
        }
        string ans = "";
        for(int i=0; i<n; ++i ){
            if (vis[i]) ans += s[i];
        }
        return ans;
    }
};

Q4：3171. 找到按位或最接近 K 的子数组

题目传送门：3171. 找到按位或最接近 K 的子数组 - 力扣（LeetCode）
题解参考”灵茶山艾府“

暴力算法非常容易想到，双层循环计算所有可能的或即可。

从左到右正向遍历 $nums$ ，对于 $x = nums[i]$ ，从 $i - 1$ 开始倒着遍历 $nums[j]$ ，更新 $nums[j] = nums[j] | x$ 。

$i = 1$ 时，我们会把 $nums[0]$ 到 $nums[1]$ 的 OR 记录在 $nums[0]$ 中。
$i = 2$ 时，我们会把 $nums[1]$ 到 $nums[2]$ 的 OR 记录在 $nums[1]$ 中， $nums[0]$ 到 $nums[2]$ 的 OR 记录在 $nums[0]$ 中。
$i = 3$ 时，我们会把 $nums[2]$ 到 $nums[3]$ 的 OR 记录在 $nums[2]$ 中； $nums[1]$ 到 $nums[3]$ 的 OR 记录在 $nums[1]$ 中； $nums[0] 到 nums[3]$ 的 OR 记录在 $nums[0]$ 中。
按照该算法，可以计算出所有子数组的 OR。注意单个元素也算子数组。

$O(n^2)$ 复杂度，很明显会超时，所以需要优化。

我们将这个问题看成一个集合的问题，那么或运算就可以当作是集合求并集操作。

进行接下来的推理需要牢记下面这个定理：

对于两个二进制数 $a$ , $b$ ,如果 $a|b=a$ ,从集合的角度上看， $b$ 对应的集合是 $a$ 对应的集合的子集。

于是我们可以对上面的暴力解法做出如下优化：

仍然是从左到右正向遍历nums，对于x=nums[i]，从i-1开始倒着遍历nums[j]:

$nums[j]|x\neq nums[j]$ ，说明nums[j]的集合可以继续扩展，则更新 $nums[j] = nums[j]|x$
否则 $nums[j]|x=nums[j]$ ,此时我们可以得出结论， $x$ 不仅是 $nums[j]$ 的子集，也是 $nums[k](k<j)$ 的子集（可以通过改变求并集顺序证明），发现等于后后面的计算就可以不用进行了，因为结果都一样，提前退出循环。
在循环中记得用 $|nums[j]-k|$ 更新答案的最小值

最后实现代码如下：

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = abs(k-nums[0]);
        for(int i=0;i<n;++i){
            ans = min(ans, abs(nums[i]-k));
            for(int j=i-1;j>=0;--j){
                int tmp = nums[j] | nums[i];
                if (nums[j]==tmp) break;
                ans = min(abs(tmp-k), ans);
                nums[j] = tmp;
            }
        }
        return ans;
    }
};

时间复杂度: $O(n log U)$ ，其中 $n$ 是 $nums$ 的长度， $U = max(nums)$ 。由于 $2^{29} - 1 < 10^9 < 2^{30} - 1$ ，二进制数对应集合的大小不会超过 $29$ ，因此在 OR 运算下，每个数字至多可以增加 $29$ 次。总体上看，二重循环的总循环次数等于每个数字可以增大的次数之和，即 $O(n log U)$ 。