上岸算法LeetCode Weekly Contest 290解题报告

【 NO.1 多个数组求交集】

解题思路

使用 Set 求交集即可。

代码展示

【 NO.2 统计圆内格点数目】

解题思路

枚举每个圆内的所有的点，将其加入到 Set 中，最后 Set 的大小即为圆内格点数目。

代码展示

【 NO.3统计包含每个点的矩形数目】

解题思路

与第四题类似，只不过变成了二维的。

先离散化处理，然后使用树状数组实现 “区间加、单点查” 的能力。

代码展示

【 NO.4花期内花的数目】

解题思路

首先进行离散化处理，start[i], end[i], person[i] 的原始数据范围都是 10^9, 实际上可以对他们进行压缩，也并不影响正确性。

比如 [[5, 10], [100, 200]], [1, 2, 3] 可以被压缩成 [[4, 5], [6, 7]], [1, 2, 3]。

压缩后我们使用树状数组实现 “区间加、单点查” 的功能，即支持如下两种操作：

• 给区间 [l, r] 加上 d
• 求点 x 的值

相当于使用树状数组维护 flowers 的差分数组的前缀和。

代码展示