Leetcode 第 290 场周赛

Posted on | Edited on | In ,
| 16k | 2:13

如题...

这是第一次在 Leetcode 上参加周赛，签了一下到😆。

2248. Intersection of Multiple Arrays

Analysis

第一个题比较简单，找出数组的交集即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        int size = nums.size();
        vector<int> cnt(1005), ret;
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < nums[i].size(); j++) {
                cnt[nums[i][j]]++;
            }
        }
        for(int i = 0; i < 1005; i++) {
            if(cnt[i] == size) ret.push_back(i);
        }
        return ret;
    }
};

这是当时自己的做法。
时间复杂度与空间复杂度都是 $O(n)$。
这样写其实有个缺陷，那就是受限于数组元素的大小，如果出现负数或者太大的数，就有问题了。
所以，应该用 map 取代普通的数组。如果不要求有序，用 unordered_map 可能会更好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        int size = nums.size();
        map<int, int> cnt;
        for(auto v: nums) {
            for(int x: v) cnt[x]++;
        }
        vector<int> ret;
        for(auto [key, val]: cnt) {
            if(val == size) ret.push_back(key);
        }
        return ret;
    }
};

这个题还可以使用 set 来模拟，依次求当前数组与 set 内元素的交集，得到的交集再与下一个数组求交集（需要有一个 tmpset 来保存结果），依次求完，最后的结果就是所有数组的交集。
不过这种做法没有用 map 的方法直接明了，所以就不写了。

6043. Count Number of Rectangles Containing Each Point

Analysis

这是第 3 个题，不过是第二个提交的题。
题意理解起来还算容易，就是求出每个点被多少个矩形包括。

Code

理解题意后，其实可以发现这不是个很复杂的题目。判断一个点是否在矩形内，只需要这个点的横纵坐标分别小于等于矩形右上端点（也就是题目给的点）的横纵坐标即可，那么很容易的就会想到暴力解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<int> ret;
        int pointnums = points.size(), rectanglenums = rectangles.size();
        for(int i = 0; i < pointnums; i++) {
            int x = points[i][0], y = points[i][1], cnt = 0;
            for(int j = 0; j < rectanglenums; j++) {
                if(x <= rectangles[j][0] &&  y <= rectangles[j][1]) cnt++;
            }
            ret.push_back(cnt);
        }
        return ret;
    }
};

这是当时提交的代码，果然，提交上去超时了。
没想到怎么优化时间复杂度，就放弃了...😂
简单分析一下，可以知道上述算法的时间复杂度是 $O(m \times n)$，其中 $m$ 是点个数，$n$ 是矩形的个数，这不超时就怪了。
后面看了别人的解题思路后，发现其实这个（准确说是这类）问题其实可以分解成 2 个子问题：

  1. 判断当前点的横坐标是不是都小于等于所有矩形的横坐标。
  2. 判断当前点的纵坐标是不是都小于等于所有矩形的纵坐标。

如果能把这两个事情放在两个单独的循环完成，或者说分开进行，然后合并 2 个结果是不是就能缩短时间复杂度了呢？
当然是的啊！虽然这个问题的解决过程肯定不可能这么理想化，不过这是一个不错的思考思路。
进一步观察题目，可以发现纵坐标的规模是 $[1, 100]$，横坐标的规模是 $[1, 10^9]$。为什么纵坐标规模这么小？显然有猫腻啊，不妨先按照相同的纵坐标，统计所有不同的横坐标的矩形：

1
2
3
4
vector<vector<int>> rec(110);
for(auto &v: rectangles) {
    rec[v[1]].push_back(v[0]);
}

由于纵坐标规模较小，所以可以直接拿来当作数组的下标。得到这样的结果后，进一步思考如何进行判断。

因为纵坐标是下标，所以可以直接找出纵坐标大于等于点的纵坐标的所有矩形（时间复杂度 $O(1)$），也即 $rec[i], i >= h$。但如果矩形的横坐标不满足条件也是不符合题意的，所以也要在这些纵坐标符合条件的矩形中，快速找出所有横坐标符合条件的矩形。
实际上，在 rec 这个数组中，每一个元素都是纵坐标相等的矩形的横坐标的集合。要完成上面说的事情，其实只需要遍历这些集合即可（此时问题已经转化了）。

到这里，回过头看可以发现，上面提到的 2 个问题，已经被拆开来分别解决了。

继续思考下去，遍历横坐标（上面提到的集合），一般是直接遍历，那样时间复杂度就是 $O(n)$。因为，外层还有 m 个点，如果直接这样遍历，估计还是够呛。有什么办法？答案是先排序，求满足条件矩形个数时再用二分查找。
排序：

1
2
3
for(auto &v: rec) {
    sort(v.begin(), v.end());
}

是的，排序可以在遍历点的循环外做完，这样就可以直接用了😂。
剩下就是遍历点，然后统计出所有的矩形就好了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        int size = points.size();
        vector<vector<int>> rec(110);
        for(auto &v: rectangles) {
            rec[v[1]].push_back(v[0]);
        }
        for(auto &v: rec) {
            sort(v.begin(), v.end());
        }
        vector<int> ret(size);
        for(int i = 0; i < size; i++) {
            int x = points[i][0], y = points[i][1];
            for(int j = y; j <= 100; j++) {
                if(!rec[j].empty()) {
                    ret[i] += rec[j].end() - (lower_bound(rec[j].begin(), rec[j].end(), x));
                }
            }
        }
        return ret;
    }
};

二分查找直接调用 lower_bound 函数来完成，做差的结果就是当前纵坐标下，所有大于等于点的横坐标的矩形个数。
不容易啊，好歹算是通过了。
现在回过头来看一下这个算法的时间复杂度：

  1. 首先按照纵坐标来统计横坐标，$O(m)$。
  2. 排序，$O(nlogn)$。
  3. 最后就是统计所有符合条件的个数，$O(m × 100 × logn)$，这个 100 可以换成字母，表示横坐标或纵坐标规模小的那个。

合计就是：$O(m) + O(nlogn) + O(H_{min} m logn)$。
对应的空间复杂度：$O(m + n)$。

没做过这类题，还真不太好想。还剩 2 道题，明天再写。

嗯，又瞅了几眼其他人的题解，发现上面这种思路是一种叫做按行统计的思路。这种思路是将纵坐标看作行，提前将横坐标提前排好序并按纵坐标大小，一行一行的保存起来，然后再逐行进行二分查找来统计符合条件的矩形总数。

如果按照只纵坐标排序，那么需要提前将矩形和点按纵坐标从大到小排序。然后在遍历点的同时，将纵坐标符合条件的矩形横坐标放入到一个新的数组 arr 中，直到不满足条件。此时，arr 中放的就是所有纵坐标符合条件的矩形横坐标，对其排序后二分查找，也一样可以算出满足条件的矩形总数。因为纵坐标是递减，所以下一个点的纵坐标一定是小于已经放入 arr 矩形的纵坐标的。剩下要做的事情，就是从剩余的矩形中找出符合当前点的横坐标的矩形横坐标，然后放入 arr 中，排序后二分。

回过头来想一想，如果在上面这种思路中也将矩形按纵坐标从大到小排好序，那在向 arr 数组中添加矩形横坐标时，不就只用遍历一次矩形横坐标了吗？
没错，确实是这样的。
所以，还是都提前排好序比较好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        sort(rectangles.begin(), rectangles.end(), [](auto &a, auto &b) { return a[1] > b[1]; });
        int size = points.size();
        vector<int> indices(size);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) { return points[i][1] > points[j][1]; });
        vector<int> ans(size), arr;
        int i = 0;
        for(int id: indices) {
            int start = i;
            while(i < rectangles.size() && rectangles[i][1] >= points[id][1]) {
                arr.push_back(rectangles[i++][0]);
            }
            if(start < i) sort(arr.begin(), arr.end());
            ans[id] = arr.end() - lower_bound(arr.begin(), arr.end(), points[id][0]);
        }
        return ans;
    }
};

如果只按照横坐标排序呢？同样的，需要先对矩形与点按横坐标从大到小排序。另外，由于纵坐标的范围比较小（$[1, 100]$），就算不用二分也是可以接受的，所以不如直接将纵坐标相同的矩形全部统计出来。然后遍历点的时候，将纵坐标满足条件的矩形个数逐个相加即可。这个方法有点类似前面提到的按行统计，但是这种方法在计算个数时会更快一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        sort(rectangles.begin(), rectangles.end(), [](auto &a, auto &b) { return a[0] > b[0]; });
        int size = points.size();
        vector<int> indices(size);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) { return points[i][0] > points[j][0]; });
        vector<int> ans(size), cnt(101);
        int i = 0;
        for(int id: indices) {
            while(i < rectangles.size() && rectangles[i][0] >= points[id][0]) {
                ++cnt[rectangles[i++][1]];
            }
            ans[id] = accumulate(cnt.begin() + points[id][1], cnt.end(), 0);
        }
        return ans;
    }
};

同样的，因为提前将点按横坐标从大到小排序了，所以也不存在遗漏与错解的情况。
em...上面提到的这些思路好像是从树状数组中来的，树状数组的概念等以后真的用到了，再说吧，这个题就到此为止了。

2251. Number of Flowers in Full Bloom

Analysis

这是第 4 个题，不过是第三个提交的题。
同样，也是因为题意理解起来比较容易，就很容易想到暴力解法。

Code

暴力解法其实很简单，只需要判断人到达的天数，在那些花儿的花期内即可，这是当时写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int fsize = flowers.size(), psize = persons.size();
        unordered_map<int, int> ht;
        for(int i = 0; i < fsize; i++) {
            int start = flowers[i][0], end = flowers[i][1];
            while(start <= end) {
                ht[start++]++;
            }
        }
        vector<int> ret;
        for(int i = 0; i < psize; i++) {
            ret.push_back(ht[persons[i]]);
        }
        return ret;
    }
};

上面这个暴力解法的时间复杂度是 $O(n^2)$，尽管明知道是超时的，还是提交一下，签个到😂。
看了一下大佬们的思路，又回头想了想，当时已经想到了这个题是按照区间（也就是花期）来统计出每一天盛开的花的数目，只是暴力遍历的方法时间消耗太大了。实际上，这里其实可以用差分的思想来做，可惜，当时我不懂（自信点，懂了可能也不会用😂）...
嗯，具体要怎么做呢？实际上与暴力代码内的统计次数类似，但是只统计两个值：start 和 end + 1。因为，花儿的花期是在 $[start, end]$ 内，所以这个区间内的花儿的盛开数量要全部加 1，也就是 start 加 1。过了花期之后，花儿盛开数量就减 1，对应的就是 end + 1 减 1。

1
2
3
4
5
map<int, int> ht;
for(auto &f: flowers) {
    ht[f[0]]++;
    ht[f[1] + 1]--;
}

这样就可以把不同花期内花儿的盛开数量统计出来了。接下来要做的事情就是，把每人到达的那一天盛开的花儿数量算出来就可以了，同样，不断累加就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> ht;
        for(auto &f: flowers) {
            ht[f[0]]++;
            ht[f[1] + 1]--;
        }
        int psize = persons.size();
        vector<int> ans(psize);
        int index = 0;
        for(int &i: persons) {
            int sum = 0;
            auto it = ht.begin();
            while(it != ht.end() && it->first <= i) {
                sum += it++->second;
            }
            ans[index++] = sum;
        }
        return ans;
    }
};

但这段代码写上去还是超时的，为什么？
看一下具体结果，前面暴力解法被卡在了样例 32，这个解法被卡在了样例 45，说明这种方法在时间上是更优秀的。那么，还有什么地方可以继续优化一下呢？
注意到，在遍历每人到达的天数时，每次都要从 ht 的开头算到尾，能想办法优化这个过程吗？因为 ht 本身已经有序了，所以完全可以先求出 ht 的前缀和（当然不管有序无序，都可以算前缀和），这样就不用重复再算了。
但是可惜的是，题目规定的 $persons[i]$ 的范围是 $[1, 10^9]$，哪里能开这么大的数组呢...
回想一下上个题，累加计算时做的优化是什么？是对下标和累加的数组提前排序，然后再累加就可以了。现在，用到这里来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> ht;
        for(auto &f: flowers) {
            ht[f[0]]++;
            ht[f[1] + 1]--;
        }
        int psize = persons.size();
        vector<int> ans(psize);
        vector<int> indices(psize);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) { return persons[i] < persons[j]; });
        int sum = 0;
        auto it = ht.begin();
        for(int &i: indices) {
            while(it != ht.end() && it->first <= persons[i]) {
                sum += it++->second;
            }
            ans[i] = sum;
        }
        return ans;
    }
};

同样，indices 也需要按下标从小到大进行排序。这样，ht 就只用遍历一次就可以算出所有 $persons[i]$ 的值了（感觉本质还是前缀和的思想）。提交上去是可以通过的...
简单分析一下，时间复杂度是 $O(nlogn) + O(mlogm) + O(n) + O(m)$，n 是 flowers 的长度，m 是 persons 的长度，前一个 $O(nlogn)$ 是 ht 底层排序消耗的时间，后面的就不说了，实际上可以直接写成 $O(nlogn) + O(mlogm)$；空间复杂度就是 $O(n + m)$。

到这里，这个题已经算是用比较简单的方法解决了。
再回顾一下差分的思想，是将每天开花的数目与每天凋谢的数目全部累加起来的。换个角度来思考，对于某一天而言，这一天开花的数目其实等于这一天之前开花的总数目减去这一天之前凋谢的花儿的总数目。如果能得到当前天之前凋谢的花儿总数目与这一天开花的总数目，二者作差之后，不就是这一天能看到的花儿总数目吗？
那么如何统计每天开花的数目与凋谢的数目呢？与前面一样，用 map 让天数与开花数目相互映射吗？这样，就又回到暴力解法去了...
实际上用 2 个数组就可以完成了。

1
2
3
4
5
6
int fsize = flowers.size();
vector<int> starts(fsize), ends(fsize);
for(auto &v: flowers) {
    starts.push_back(v[0]);
    ends.push_back(v[1]);
}

接着，再用上一题求和的方法：排序和二分。
前一天开花的数目，

1
2
3
4
5
6
7
8
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int psize = persons.size();
vector<int> ans(psize);
for(int i = 0; i < psize; i++) {
    ans[i] = (upper_bound(starts.begin(), starts.end(), persons[i]) - starts.begin()) - 
             (lower_bound(ends.begin(), ends.end(), persons[i]) - ends.begin());
}

最后合并起来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int fsize = flowers.size();
        vector<int> starts(fsize), ends(fsize);
        for(auto &v: flowers) {
            starts.push_back(v[0]);
            ends.push_back(v[1]);
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        int psize = persons.size();
        vector<int> ans(psize);
        for(int i = 0; i < psize; i++) {
            ans[i] = (upper_bound(starts.begin(), starts.end(), persons[i]) - starts.begin()) - 
                     (lower_bound(ends.begin(), ends.end(), persons[i]) - ends.begin());
        }
        return ans;
    }
};

就可以求得最终结果了...
时间复杂度：$O((n + m)logn)$。
空间复杂度：$O(n)$。

2249. Count Lattice Points Inside a Circle

Analysis

好的，现在再回到第二题。
这个题当时没什么思路，原因是不知道怎么枚举。题意倒是比较简单，给定一定数量的圆，返回至少出现在一个圆内的格点数目。格点的定义题目已经解释了，其实就是坐标为整数的点，并且离圆心的距离小于等于半径。

Code

现在想想，其实可以想出暴力解法（可能是分析前面题目的经验吧）。因为圆心、半径给的都是整数，所以，每个圆一定会外切一个矩形，按照这个矩形的左下端点和边长进行枚举，再判断是否满足条件。为了避免重复，可以利用 set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        map<pair<int, int>, int> points;
        for(auto v: circles) {
            int l = v[0] + v[2], h = v[1] + v[2], r = v[2];
            int leftlowerx = v[0] - v[2], leftlowery = v[1] - v[2];
            for(int i = leftlowerx; i <= l; i++) {
                for(int j = leftlowery; j <= h; j++) {
                    int dis = (i - v[0]) * (i - v[0]) + (j - v[1]) * (j - v[1]);
                    if(dis <= r * r) points[make_pair(i, j)] = 1;
                }
            }
        }
        return points.size();
    }
};

因为 set 与 pair 一起使用时要重新写下 hash 函数（遗憾的是...我不知道 C++ 这个怎么写😂），就直接用 map 了。可惜的是，方向是找对了，就是还是超时了，死在第 57 个样例了。
看了下提示：Since you need to reduce the search space, consider the minimum and maximum possible values of the coordinates of a lattice point contained in any circle.。
想了下，枚举每个圆的外切矩形一定会有很多重复的点，如果我们直接从能容纳所有圆的那个最大的外切矩形坐标开始枚举，再利用 hash 不就可以减少重复比较的次数了吗？
是的，就是这样的...感谢提示~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        int leftlowerxmin = INT_MAX, leftlowerymin = INT_MAX;
        int lmax = INT_MIN, hmax = INT_MIN;
        for(auto &v: circles) {
            int l = v[0] + v[2], h = v[1] + v[2];
            int leftlowerx = v[0] - v[2], leftlowery = v[1] - v[2];
            if(l > lmax) lmax = l;
            if(h > hmax) hmax = h;
            if(leftlowerx < leftlowerxmin) leftlowerxmin = leftlowerx;
            if(leftlowery < leftlowerymin) leftlowerymin = leftlowery;
        }
        map<pair<int, int>, int> latticepoints;
        for(int i = leftlowerxmin; i <= lmax; i++) {
            for(int j = leftlowerymin; j <= hmax; j++) {
                if(latticepoints.count(make_pair(i, j))) break;
                for(auto &v: circles) {
                    int dis = (i - v[0]) * (i - v[0]) + (j - v[1]) * (j - v[1]);
                    if(dis <= v[2] * v[2]) {
                        latticepoints[make_pair(i, j)] = 1;
                        break;
                    }
                }
            }
        }
        return latticepoints.size();
    }
};

这个其实也是暴力解法，只是转换了一下思考的角度...
突然发现，好像前面的暴力解法，忘记用 hash 的性质了...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        map<pair<int, int>, int> points;
        for(auto v: circles) {
            int l = v[0] + v[2], h = v[1] + v[2], r = v[2];
            int leftlowerx = v[0] - v[2], leftlowery = v[1] - v[2];
            for(int i = leftlowerx; i <= l; i++) {
                for(int j = leftlowery; j <= h; j++) {
                    if(points.count(make_pair(i, j))) continue;
                    int dis = (i - v[0]) * (i - v[0]) + (j - v[1]) * (j - v[1]);
                    if(dis <= r * r) points[make_pair(i, j)] = 1;
                }
            }
        } 
        return points.size();
    }
};

加上 hash 后竟然通过了...😂，就是时间、空间消耗惨不忍睹。
看了下大佬们的思路，这个题好像还有其他解法，懒得继续思考了，这个题就到此为止了...

Summary

现在回头看一下这次场周赛的题目，感觉 4 个题有点类似，特别是第 2 题、第 3 题和第 4 题，都有数学的影子在里面。另外，这几个题好像的题目形式都与树状数组有点关系，等之后研究一下再来看看吧。
不过现在再回头看看，感觉好像也不是特别复杂的题目（我在说什么 P 话😂）。
哈哈，当时做的时候还是问题很多的，现在疑惑差不多就解决了，反而觉得不难了...
真是应了那句话了：难者不会，会者不难。不过，我想，现在的“会者”也是从曾经的“难者”一步一步过来的吧...

Buy me a coffee ? :)
0%