LeetCode周赛293，高质量的思维与数据结构题
大家好，日拱一卒，我是梁唐。本文始发于公众号Coder梁
今天我们照惯例来聊聊昨天上午的LeetCode周赛，这一次比赛的赞助商是中国银联，算是知名国企。当年我毕业的时候，薪水最高的同学就是去的银联。
这一次前500名就可以获得内推机会，但吐槽一下，500名也不是这么容易的。尤其是最近，可能是因为疫情影响，参加周赛的人越来越多……以前只要四题全出，至少500名，现在还得拼手速……
这一场的题目难度还是可以的，尤其是最后一题很有难度，算是比较硬核的数据结构题。
这里分享一个小技巧，在赛后我们是可以看到所有人提交的代码的。这个也是线上比赛的常规操作，这样方便大家进行检举监督，可以举报作弊，也可以让大家看到大牛的代码进行学习。
我们进入比赛榜单页面，点击提交时间之前的代码logo，就可以看到大牛提交的源码了。
点开之后：
这是一个很好的学习方式，除了可以学到算法以外，还能学到很多代码的技巧。对于提升自己是很有帮助的。
我们，接下来我们进入正题，来看看这次的题目吧。
移除字母异位词后的结果数组
给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。
在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：
- 0 < i < words.length
- words[i - 1] 和 words[i] 是 字母异位词 。
只要可以选出满足条件的下标，就一直执行这个操作。
在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。
题解
这题有几个坑，第一个坑是字符串比较字母异位词，这意味着我们需要去分析字符串的字母构成，如果采用暴力的方法，我们需要统计字符串当中每个字母出现的次数，然后再对比两个字符串之间字母的构成是否相等。显然这非常麻烦。
有一个解决的小技巧就是排序，我们直接将字符串排序，如果排序之后的字符串相等，那么它们就是字母异位词，否则就不是。
第二个坑是这个操作可能执行很多次，实际上这个是出题人的障眼法。我们假设一下这个样例：[a, a, a, b, c, c]。相同的字母表示字母异位词，那么无论我们按照什么顺序进行删除，a和c之间永远是间隔的，b不能被删掉。所以c是不可能影响a的，也就是说字母异位词之间互相影响的前提是连续，只有连续的才会影响。
那么我们只需要遍历一次，凡是和前一位字母构成不同的字符串都是答案。
由于我们对字符串排序会产生修改，所以我们需要先拷贝一份用来判断。
class Solution {
public:
vector<string> removeAnagrams(vector<string>& words) {
int n = words.size();
// 拷贝一份，排序之后用来判断字母异位词
vector<string> wd = words;
vector<string> ret;
for (int i = 0; i < n; i++) {
sort(wd[i].begin(), wd[i].end());
}
ret.push_back(words[0]);
for (int i = 1; i < n; i++) {
if (wd[i] != wd[i-1]) {
ret.push_back(words[i]);
}
}
return ret;
}
};
不含特殊楼层的最大连续楼层数
Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。
给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。
返回不含特殊楼层的 最大 连续楼层数。
题解
这题我比赛的时候脑残了，只粗略看了一眼数据范围， 没有仔细看其中的说明。其实当中明确说了，bottom 和 top就是所有楼层中最小和最大的。那么也就不需要考虑小于bottom和超出top的情况。
如果a和b是两个相邻的特殊楼层，那么它们中间的普通楼层数量是b - a - 1，如果a是bottom或b是top，那么答案是b - a。也就是说边界的情况和中间普通的情况相差了1。我们当然可以对头尾的情况进行特判，还有一个比较简单的方法就是将bottom-1和top+1视作是两个特殊楼层，这样它们的计算方式就统一了。
这样一来，代码也会变得非常简单：
class Solution {
public:
int maxConsecutive(int bottom, int top, vector<int>& sp) {
sp.push_back(bottom - 1);
sp.push_back(top + 1);
sort(sp.begin(), sp.end());
int n = sp.size();
int ret = 0;
for (int i = 1; i < n; i++) ret = max(ret, sp[i] - sp[i-1] - 1);
return ret;
}
};
按位与结果大于零的最长组合
对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。
- 例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
- 同样，对 nums = [7] 而言，按位与等于 7 。
给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 candidates 中的每个数字在每种组合中只能使用 一次 。
返回按位与结果大于 0 的 最长 组合的长度*。*
题解
看一下数据范围，极端的情况下candidate的数量能有1e5，如果题目做得多的话，看到这个范围就能反应过来，正解的复杂度大概率是O(nlogn)O(n\log n)O(nlogn)，至少n方的复杂度是肯定不行的。
分析完数据范围之后，我们再来解读题意。我们要找到最长的与操作之后大于0的长度，和最长不下降子序列非常相似。但仔细分析，会发现本题没有最优子结构，按位与运算大于0的结果不具有传递性。a & b > 0, b & c > 0不代表a & b & c > 0，所以这种动态规划的方法是行不通的。
不知道有没有同学在这里被卡住的，卡住的时候，往往说明还有一些线索或者是推论我们没有发现。算法题难，很多时候就难在这里，有一些推论题目当中不会明确说明，需要我们自己通过分析和思考发现。
本题当中要求按位与操作之后大于0，有没有想过什么情况下才能按位与操作大于0呢？如果熟悉二进制的话，其实很简单，就是至少有一个二进制位，所有操作的这些数上都为1。我们要找所有数当中按位与操作之后大于0的最长长度，其实就是在问，这些数的二进制位当中，值为1的数量的最大值。
所以理解到这里，剩下的就非常简单了，我们就统计一下所有二进制位为1的数量，其中的最大值就是答案。
写成代码真的很简单，但把这一连串推导下来才是最难的。
class Solution {
public:
int largestCombination(vector<int>& cand) {
int n = cand.size();
int ret = 0;
for (int i = 0; i < 30; i++) {
int cur = 0;
for (int j = 0; j < n; j++) {
if (cand[j] & (1 << i)) {
cur++;
}
}
ret = max(ret, cur);
}
return ret;
}
};
统计区间中的整数数目
给你区间的 空 集，请你设计并实现满足要求的数据结构：
- **新增：**添加一个区间到这个区间集合中。
- **统计：**计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类：
- CountIntervals() 使用区间的空集初始化对象
- void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
- int count() 返回出现在 至少一个 区间中的整数个数。
**注意：**区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。
题解
区间覆盖求覆盖长度，典型的数据结构题，基本上就是裸的区间线段树，虽然算法明摆着，但在比赛的时候看到还是挺绝望的。毕竟我没有为比赛专门准备模板，我也不喜欢这样，毕竟比赛的结果不重要，重要的是锻炼自己的能力。
区间合并覆盖的问题，可以使用之前介绍过的珂朵莉树。但在使用的过程当中有一个坑，在求当前所有覆盖长度时，如果遍历所有区间进行求和，会导致超时。所以势必就需要我们在插入区间的时候就维护好当前覆盖的总长，然而这又会带来另外一个问题，我们在插入区间的时候会批量删除一部分区间，我们需要把这部分区间的长度减去。
在模板中的代码是批量删除的：
void assign(int l, int r, int v) {
auto itr = split(r), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node_t(l, r, v));
}
我们需要改成手动删除，这里有一个坑，我一开始是这样写的：
void assign(int l, int r, int v) {
auto itr = split(r), itl = split(l);
for (auto it = itl; it != itr; it++) {
if (it->v != -1) {
ret -= (it->r - it->l);
}
odt.erase(it);
}
odt.insert(Node_t(l, r, v));
}
看起来逻辑没啥问题，但其实有一个隐藏的bug。就是当容器erase的时候，迭代器的指针指向的元素也会随之变化。我们使用这种方式来遍历是可以的，但不能一边遍历一边删除或添加。
正解是容器在erase的时候会返回下一个元素的迭代器，所以应该这么写：
void assign(int l, int r, int v) {
auto itr = split(r), itl = split(l);
for (auto it = itl; it != itr; it = odt.erase(it)) {
if (it->v != -1) {
ret -= (it->r - it->l);
}
}
odt.insert(Node_t(l, r, v));
}
完整代码：
struct Node_t {
int l, r;
mutable int v;
Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
inline bool operator<(const Node_t &o) const { return l < o.l; }
};
class CountIntervals {
public:
set<Node_t> odt;
int n = 1e9+10;
int ret = 0;
CountIntervals() {
odt.insert(Node_t{0, n, -1});
}
auto split(int x) {
if (x > n) return odt.end();
auto it = --odt.upper_bound(Node_t{x, 0, 0});
if (it->l == x) return it;
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node_t(l, x, v));
return odt.insert(Node_t(x, r, v)).first;
}
void assign(int l, int r, int v) {
auto itr = split(r), itl = split(l);
for (auto it = itl; it != itr; it = odt.erase(it)) {
if (it->v != -1) {
ret -= (it->r - it->l);
}
}
odt.insert(Node_t(l, r, v));
}
void add(int left, int right) {
assign(left, right + 1, 0);
ret += right - left + 1;
}
int count() {
return ret;
}
};
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* obj->add(left,right);
* int param_2 = obj->count();
*/
其实这题也可以不用珂朵莉树，直接使用set来维护所有的区间一样是可以的。
我们使用set存储所有区间，每次插入新的区间的时候把所有可能重叠的区间全部删掉，插入合并之后的完整区间。核心原理和珂朵莉树的方法是一样的，只不过珂朵莉树会拆分区间，这种做法更加简单粗暴，直接全部删除。虽然我们每次都会删除一堆区间，但从源头分析，每个区间只会进出set一次，所以总体的复杂度依然是O(nlogn)O(n \log n)O(nlogn)。
struct Node_t {
int l, r;
mutable int v;
Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
inline bool operator<(const Node_t &o) const { return l < o.l; }
};
class CountIntervals {
public:
int ret = 0;
set<pair<int, int>> st;
CountIntervals() {
}
void add(int left, int right) {
auto it = st.lower_bound(make_pair(left, left));
if (it != st.begin()) it--;
int l = left, r = right;
vector<pair<int, int>> to_erase;
while (it != st.end() && it->first <= right) {
if (it->second < left) {
it++;
continue;
}
l = min(it->first, l);
r = max(it->second, r);
to_erase.push_back(*it);
it++;
}
for (auto v : to_erase) {
ret -= (v.second - v.first + 1);
st.erase(v);
}
st.insert(make_pair(l, r));
ret += r - l + 1;
}
int count() {
return ret;
}
};
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* obj->add(left,right);
* int param_2 = obj->count();
*/
最后是线段树的做法，在比赛的时候还是有些抵触的，毕竟调试太花费时间了，实在是很难有自信一次性写对。另外一点是我当时看到1e9的范围被吓到了，感觉用线段树会空间越界，所以也没有往这方面细想。其实空间复杂度的问题有办法解决，使用懒惰操作就可以了。
但赛后实际写一下，发现并没有很困难。首先，这个线段树没有建树的步骤。因为一开始没有任何区间， 可以理解成全集上都是空的。也就是[1, 1e9+1)的区间全部都为0。一开始的时候只有这一个节点，每次只在需要拆分节点的时候拆分线段树。
我们每次查询求的都是整个空间的解，因此query步骤也可以省略，只需要实现update即更新的部分即可。
在这题当中，只有一个更新操作，把一个区间从0置为1。也就是说如果一个区间已经全部都为1，那么它将不再发生变化。
由于区间长度非常大，有1e9，所以我们没办法直接把完整的树建好，只能在一边查询一边创建。由于区间只会被覆盖一次，没有被创建的区间一定全为0，否则之前就已经创建了。这里的逻辑有些难想到，但理清楚了不算太难理解。如果还觉得困难，可以参考一下代码：
struct P {
// 维护区间左右端点，以及当前被覆盖的长度
int l, r, v;
P *lef, *rig;
P(){}
P(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv), lef(nullptr), rig(nullptr) {}
void update(int ll, int rr) {
// 如果覆盖的区间包含[l, r)，或者当前区间已经被覆盖，直接返回
if (ll <= l && rr >= r || v == r - l) {
v = r - l;
return ;
}
int m = (l + r) >> 1;
// 拆分区间
if (lef == nullptr) lef = new P(l, m, 0);
if (rig == nullptr) rig = new P(m, r, 0);
// 递归调用
if (ll < m) lef->update(ll, rr);
if (rr > m) rig->update(ll, rr);
// 更新当前节点
v = lef->v + rig->v;
}
};
完整代码：
struct P {
int l, r, v;
P *lef, *rig;
P(){}
P(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv), lef(nullptr), rig(nullptr) {}
void update(int ll, int rr) {
if (ll <= l && rr >= r || v == r - l) {
v = r - l;
return ;
}
int m = (l + r) >> 1;
if (lef == nullptr) lef = new P(l, m, 0);
if (rig == nullptr) rig = new P(m, r, 0);
if (ll < m) lef->update(ll, rr);
if (rr > m) rig->update(ll, rr);
v = lef->v + rig->v;
}
};
class CountIntervals {
public:
P* rt;
CountIntervals() {
rt = new P(1, 1e9+10, 0);
}
void add(int left, int right) {
rt->update(left, right+1);
}
int count() {
return rt->v;
}
};
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* obj->add(left,right);
* int param_2 = obj->count();
*/
虽然看代码并不算长，但大佬们在比赛的时候能几分钟写完，真的是不跪不行……