leetcode 第 400 场算法比赛

零、背景

这次比赛都不难，不过我手速慢了点，最后1题大意了没有闪，还错了一次。

A: 栈模拟。
B: 区间合并。
C: 贪心。
D: 线段树。

排名：166 代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/400

一、候诊室中的最少椅子数

题意：一个数字不断的加一和减一，求这个数字期间的最大值。

思路：栈模拟，这里不关心数值，所以只是使用一个数字来代替栈。

加一时数字就加一，减一时就减一，每次求 max 即可。

二、无需开会的工作日

题意：工作时长有 n 天，给一些会议列表，一个会议会跨越多个工作日，问有多少天是没有会议的。

思路：区间合并的经典题型。

需要先对区间进行排序，开始时间较早的在前面，同时开始时，结束时间的顺序无所谓。

对于这道题，有两个思路。
第一个方法是先求出所有会议天数，总天数减去会议天数，就是答案。
第二个方法是直接在合并区间时，求出答案。

这里建议使用第一个方法，不需要特殊处理边界。

代码如下，

// pre = firstDay
// [a,b]
pre = max(pre, a);
ans += max(0, b - pre + 1);
pre = max(pre, b+1);

当然，比赛的时候我使用的第二个方法，稍微浪费了一些时间。

三、删除星号以后字典序最小的字符串

题意：给一个字符串，需要删除所有的字符 * , 删除这个字符时，需要同时删除前面的任意一个最小字符。
问所有字符 * 都删除后，剩余的字符串的最小字典序是什么。

思路：贪心。

贪心1：目标是字典项最小，对于多个最小字符，显然删除最后一个最小字符最优。

贪心2：对于多个 * ，右边的删除区间包含左边的，可以证明，从左到右删除最优。

证明：
首先可以发现，每删除一个最小字符，新的字符串的字典序就会变大。

这里假设只有两个*，且只有一个最小字符在左区间，只有一个次小字符在右区间。
情况1：先删除左边，再删除右边时，最小字符和次小字符都被删除。
情况2：先删除右边时，左边的最小字符被删除。再删除左边时，左边没有最小字符了，只能删除其他字符，这就导致左边多删除一次最小字符。

分析可以发现，情况2有概率比情况1多删除一次最小字符，从而导致情况1的字典序比情况2更大。
故需要每次都先删除左边，再删除右边，即需要从左到右删除。

如何找到左边的最小值？
统计每个字符的下标升序列表。
从小到大枚举字符，找到的第一个字符就是最小字符，下标列表里最后一个就是最后一个最小字符。

四、找到按位与最接近 K 的子数组

题意：给一个数组，求一个子数组，使得子数组的且位运算后与 K 的距离最小，求最小距离。

思路：线段树。

可以发现，以某个下标为第一个元素的所有子数组，数组越长，位运算的值越小，即满足有序性。

想要找到与 K 距离最接近的下标，只需要二分找到首个大于等于 K 的子数组，枚举左右边界，即可找到最小值。

如何快速求出一个子数组的答案呢？
一个子数组对应一个区间，这个就是一个区间查询问题，显示可以使用线段树来优化。

边界问题：线段树初始化时，边界可能比实际数组元素大，此时需要初始化为 (1<<n) - 1。

注意事项：这里的有序性是递减的，不要写成递增的二分查找了。

五、最后

这次比赛最后一题错了一次，原因是写二分查找时，把有序性当做递增处理了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code