LeetCode周赛290，题解合集
大家好，日拱一卒，我是梁唐。本文始发于公众号：Coder梁
今天是周一，我们老规矩来看昨天上午的LeetCode周赛第290场。这一场比赛的赞助商是华为，应该说是目前为止赞助商当中规模最大的公司了。
个人感觉这一场比赛的题目质量虽然还不错，但设置不是非常合理，原因我之后再说。
这一次发挥也还行，由于错了两次罚时掉出了前200：
废话不多说了，我们来看题吧。
多个数组求交集
给你一个二维整数数组 nums ，其中 nums[i] 是由 不同 正整数组成的一个非空数组，按 升序排列 返回一个数组，数组中的每个元素在 nums 所有数组 中都出现过。
题解
比赛的时候比较紧张，拿到手就写，最先写的是暴力求解的思路。由于Python当中list可以直接转换成set，所以就选了Python。
但写了一半的时候发现不对，暴力并不是很好的方法，并且有可能超时。
我们来简单分析一下，首先，我们枚举所有的元素，复杂度是O(n2)O(n^2)O(n2)，其次我们要遍历所有的set，判断元素是不是在所有的set中都能找到。复杂度是O(n)O(n)O(n)。乘在一起，总体的复杂度在O(n3)O(n^3)O(n3)。这里的n的范围是1000，基本上一定会超时。
转变思路的原因是因为觉得在所有set中都出现这个判断条件有些复杂，因为对于每一个元素都需要遍历所有的set。
那有没有办法不用枚举直接判断呢？
优化点就在这里，我们只要稍稍转变思路，存储一下每一个元素出现的list的数量。由于题目中说了，nums[i]中的元素各不相同，所以出现次数和list数量相等的，就是在所有list中都出现的元素。
所以思路就是遍历所有的元素，维护每个元素出现的list的数量，找出其中出现数量和list数量相等的元素，进行排序返回。
赛场上我用了Python，其实C++也一样求解。
class Solution:
def intersection(self, nums: List[List[int]]) -> List[int]:
dt = defaultdict(int)
n = len(nums)
for l in nums:
for v in l:
dt[v] += 1
ret = []
for k, v in dt.items():
if v == n:
ret.append(k)
return sorted(ret)
C++ 版本：
class Solution {
public:
vector<int> intersection(vector<vector<int>>& nums) {
int n = nums.size();
map<int, int> mp;
for (auto &ns: nums) {
for (auto v : ns) {
mp[v]++;
}
}
vector<int> ret;
for (auto it = mp.begin(); it != mp.end(); it++) {
int k = it->first, v = it->second;
if (v == n) {
ret.push_back(k);
}
}
sort(ret.begin(), ret.end());
return ret;
}
};
统计圆内格点数目
给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。
注意：
- 格点 是指整数坐标对应的点。
- 圆周上的点 也被视为出现在圆内的点。
题解
求若干个圆覆盖的点的数量，不妨思考最简单的情况，即只有一个圆的情况。
只有一个圆时，我们可以遍历将这个圆包裹的最小正方形中的所有点，计算每一个点到圆心的距离。所有距离小于等于半径的点，都在圆上或圆内：
多个圆其实可以同样处理，只不过由于圆之间会存在交叉的部分， 这个部分的点不能重复添加。因此我们需要使用一个数据结构来避免重复。要去重，最好的数据结构当然是set。
所以我们使用set维护所有被覆盖的点的坐标，最后返回set中的元素个数即可。
class Solution {
public:
double dis(double x, double y, double x1, double y1) {
return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
int countLatticePoints(vector<vector<int>>& circles) {
typedef pair<int, int> pii;
set<pii> st;
for (auto cir : circles) {
int x = cir[0], y = cir[1], r = cir[2];
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
double d = dis(x, y, i, j);
if (r - d > -1e-8) {
st.insert(make_pair(i, j));
}
}
}
}
return st.size();
}
};
我们通过距离来判断是否在圆中，按道理判断条件时r - d >= 0。但由于距离是一个浮点数，浮点数比较相等时会受到精度的影响，所以我们可以写成：r - d > -1e-8，即让它们的差大于一个极逼近0的负数，这也是计算几何的常见套路。
统计包含每个点的矩形数目
给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。
第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 。
请你返回一个整数数组 count ，长度为 points.length，其中 count[j]是 包含 第 j 个点的矩形数目。
如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。
题解
我们先来聊正解，按正解来，这题应该是一道偏序排序的问题。
理解题意之后可以发现，对于每一个查询 (x, y)，我们要做的是找到包含这个点的矩形的数量。而要包含这个点，意味着li >= x, hi >= y，即右上角在该点的右上方。
但由于一个点的坐标值有两个维度，我们很难直接快速找到满足要求的数量。突破口在于数据的范围：
我们可以注意到，给定的坐标当中x的范围很大，最大有1e9，而y的范围很小，最大只有100。那么很显然，这个100就是我们的突破口。
所以我们不难想到可以先按照y轴对点进行合并，将y轴值相等的点放在一起，之后再按照x轴排序。由于y轴最多只有100个值，意味着我们最多进行100次排序。
对于每一个查询(xi, yi)，我们只需要遍历y轴坐标在[yi, 100]范围的集合。由于每个集合的x已经排好序了，所以我们可以直接二分找到大于等于xi的位置。我们把所有符合的y轴范围内的数量相加就是答案：
class Solution {
public:
vector<int> countRectangles(vector<vector<int>>& rect, vector<vector<int>>& points) {
vector<vector<int>> nums(102, vector<int>());
for (auto &vt: rect) {
int x = vt[0], y = vt[1];
// 把y轴相同的放入同一个vector
nums[y].push_back(x);
}
for (int i = 1; i <= 100; i++) {
// 对于每一个y对应的vector排序
sort(nums[i].begin(), nums[i].end());
}
vector<int> ret;
for (auto &vt: points) {
int x = vt[0], y = vt[1];
int cur = 0;
// 遍历所有大于等于y的vector，通过二分计算数量
for (int i = y; i <= 100; i++) {
cur += nums[i].end() - lower_bound(nums[i].begin(), nums[i].end(), x);
}
ret.push_back(cur);
}
return ret;
}
};
但这题有更简单粗暴的解法，就是二维树状数组。对于知道二维树状数组的同学，这道题几乎就是裸题。
树状数组可以动态求解某一个区间内的总和，二维树状数组可以求解某个二维区间内的总和。对于矩形(li, hi)来说，它可以覆盖(0 <= x <= li, 0 <= y <= hi)范围内的所有点，相当于给这个二维区间增加了1。
对于每一个查询(xi, yi)，我们要求的就是(x >= xi, y >= yi)范围内的和。
不过还有一个问题，二维树状数组需要使用到二维数组。但在这题当中，由于x轴的范围太大，有1e9，如果我们直接创建二维数组是一定会内存不够的。所以为了节省空间，我们还需要对x轴的坐标进行离散化。
简单介绍一下离散化，离散化是说在我们只关心数据大小关系而不关心具体的值时，将原本大范围的数据进行缩放的操作。
比如说我们需要用到数组中这些下标：[1, 1000, 20000, 300000]，那么我们要创建的数组就会非常大，而且其中绝大多数都被浪费了。在我们不关心下标具体值只关心大小关系的情况下，我们可以将它们重新映射到[0, 1, 2, 3]。这样我们数组长度只需要4就足够存下了。
比如在这题当中，虽然x轴的范围最大能有1e9，但矩形的数量最多也就1e5，对于这题而言，坐标的值其实并不重要，我们更关心是坐标之间的大小关系。所以我们可以把x轴上的点保留它们的大小关系重新映射，这样的操作就叫做离散化。
class Solution {
public:
int arr[100050][102], N = 100001, M = 101;
int lowbit(int x) {
return x & (-x);
}
void update(int x, int y) {
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
arr[i][j] += 1;
}
}
}
int query(int x, int y) {
int ret = 0;
for (int i = x; i < N; i += lowbit(i)) {
for (int j = y; j < M; j += lowbit(j)) {
ret += arr[i][j];
}
}
return ret;
}
vector<int> countRectangles(vector<vector<int>>& rect, vector<vector<int>>& points) {
vector<int> xi;
// 所有需要离散化的x
for (auto vt: rect) {
xi.push_back(vt[0]);
}
for (auto vt: points) {
xi.push_back(vt[0]);
}
// 排序
sort(xi.begin(), xi.end());
int idx = 1;
map<int, int> mp;
// 使用map存储离散化的映射关系
for (auto v: xi) {
if (mp.count(v)) continue;
mp[v] = idx++;
}
// 套用二维树状数组进行更新
for (auto vt : rect) {
int x = mp[vt[0]], y = vt[1];
update(x, y);
}
vector<int> ret;
for (auto vt: points) {
// 查询时要记得求的是映射之后的范围
int x = mp[vt[0]], y = vt[1];
int cur = query(x, y) ;
ret.push_back(cur);
}
return ret;
}
};
花期内花的数目
给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。
题解
如果说第三题是二维树状数组的裸题的话，那么第四题就是一维树状数组的裸题。
读完题目之后会发现这是一道经典的区间覆盖问题，直接一维树状数组可以搞定。对于花朵i来说，它的开花时间是[starti, endi]，那么我们只需要update(starti, 1), update(endi+1, -1)即可。
也就是说从starti位置开始，之后的区间和增加1，从endi + 1位置开始，之后的区间和减去1。这样一来，一加一减抵消，只有[starti, endi]范围内的区间和增加了1。这是使用树状数组求解区间覆盖问题的经典做法。
同样和上一题一样，区间的范围可能非常大，有1e9，而花朵的数量只有1e4，所以我们需要进行离散化。
老实讲我在比赛的时候看到这题的时候都惊呆了，直接把第三题的代码拷贝过来稍微改了改就通过了……
class Solution {
public:
const int N = 500050;
int arr[500050] = {0};
int lowbit(int x) {
return x & (-x);
}
void update(int u, int x) {
for (int i = u; i < N; i+= lowbit(i)) {
arr[i] += x;
}
}
int query(int u) {
int ret = 0;
for (int i = u; i > 0; i -= lowbit(i)) {
ret += arr[i];
}
return ret;
}
vector<int> fullBloomFlowers(vector<vector<int>>& fl, vector<int>& pl) {
map<int, int> mp;
vector<int> ti;
for (auto f : fl) {
ti.push_back(f[0]);
ti.push_back(f[1]+1);
}
for (auto p : pl) {
ti.push_back(p);
}
int idx = 1;
sort(ti.begin(), ti.end());
for (auto v : ti) {
if (mp.count(v)) continue;
mp[v] = idx++;
}
for (auto f : fl) {
int s = mp[f[0]], e = mp[f[1]+1];
update(s, 1);
update(e, -1);
}
vector<int> ret;
for (auto v: pl) {
ret.push_back(query(mp[v]));
}
return ret;
}
};
当然这题不使用树状数组也有解法，其实思路和离散化差不多。
就是把花朵数量发生变化的点记录下来，也就是starti和endi，我们使用一个临时变量标记当前开花的数量。遇到starti就+1，遇到endi就-1，遇到查询就记录。
但是实现的时候有一些细节，我们记录的是发生变化的位置，和发生变化的种类。但当同一个位置有多个点，比如说既是一朵花的开始，又是一朵花的结尾，又有一个查询。这个时候符合题意的执行顺序是怎样的？我们怎么样保证它们的顺序？
显然，符合题意的顺序是先+1， 再查询，最后-1。也就是说花期结束时最后执行的，花期开始是最先执行的，查询则放在中间，在花期开始之后，在花期结束之前。
我们怎么保证我们排序之后，x相同的位置能按照我们的期望排序呢？这里有一个很巧妙的思路，就是利用C++对于pair排序时的特性，在第一个关键字相同时会自动对比第二个关键字。我们只需要在第二个关键字做文章，就可以保证得到我们预期的排序顺序。
由于花期开始我们期望它最先执行，所以它的第二个值放INT_MIN，即最小的整数，这样可以保证在同样x中它最靠前。花期结束我们期望它最后执行，所以我们放入INT_MAX，对于查询，我们就放入它的查询序号，刚好在最大和最小中间。
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& fl, vector<int>& pl) {
typedef pair<int, int> pii;
vector<pii> dat;
for (auto f : fl) {
dat.push_back(pii(f[0], INT_MIN));
dat.push_back(pii(f[1], INT_MAX));
}
for (int i = 0; i < pl.size(); i++) {
dat.push_back(pii(pl[i], i));
}
sort(dat.begin(), dat.end());
vector<int> ret(pl.size(), 0);
int cur = 0;
for (auto &v : dat) {
if (v.second == INT_MIN) {
cur++;
}else if (v.second == INT_MAX) {
cur--;
}else {
ret[v.second] = cur;
}
}
return ret;
}
};
这个解法是我赛后看到大神题解之后才想到的，比赛的时候第一反应就是树状数组秒水题。
所以4题当中，有两题可以当做树状数组水题来说，只要你会树状数组和离散化这两个算法，那么这两题就几乎没有难度。
并不是说LeetCode比赛就一定不能出树状数组的问题，但一连两题都可以被同一种算法解决，显然不太合适。对于会的同学来说成了手速场，比的就是谁的手速快，对于不会的同学来说，则相当绝望，眼看着一堆人通过，但自己就是毫无办法。
因此，从这点上来说，这场周赛的题目设置是有一些问题的。
转载自:https://juejin.cn/post/7090421361394319374