上岸算法 | LeetCode Weekly Contest 第 290 场周赛解题报告
### 多个数组求交集使用 Set 求交集即可。
```Java
class Solution {
public List<Integer> intersection(int[][] nums) {
List<Integer> result = new ArrayList<>();
if (nums.length == 0) {
return result;
}
List<Integer> list = toList(nums);
for (int i = 1; i < nums.length; i++) {
list = intersection(list, toList(nums));
}
Collections.sort(list);
return list;
}
private List<Integer> toList(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
list.add(num);
}
return list;
}
private List<Integer> intersection(List<Integer> list1, List<Integer> list2) {
List<Integer> result = new ArrayList<>();
Set<Integer> set = new HashSet<>(list1);
for (int n : list2) {
if (set.contains(n)) {
result.add(n);
set.remove(n);
}
}
return result;
}
}
```
### 统计圆内格点数目
枚举每个圆内的所有的点，将其加入到 Set 中，最后 Set 的大小即为圆内格点数目。
```Java
class Solution {
public int countLatticePoints(int[][] circles) {
Set<Long> points = new HashSet<>();
for (int[] circle : circles) {
int x = circle;
int y = circle;
int r = circle;
// 出于便利，直接枚举正方形区域，然后判断是否在圆内
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
if (Math.abs(i - x) * Math.abs(i - x) + Math.abs(j - y) * Math.abs(j - y) <= r * r) {
points.add((long) i << 32 | j); // 使用 long 的高 32 位表示 x 坐标，低 32 位表示 y 坐标
}
}
}
}
return points.size();
}
}
```
### 统计包含每个点的矩形数目
与第四题类似，只不过变成了二维的。
先离散化处理，然后使用树状数组实现 “区间加、单点查” 的能力。
```Java
class Solution {
public int[] countRectangles(int[][] rectangles, int[][] points) {
List<Integer> xs = new ArrayList<>();
for (int[] point : points) {
xs.add(point);
}
for (int[] rectangle : rectangles) {
xs.add(rectangle);
}
Collections.sort(xs);
xs = new ArrayList<>(new LinkedHashSet<>(xs));
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < xs.size(); i++) {
map.put(xs.get(i), i + 1);
}
for (int[] point : points) {
point = map.get(point);
}
for (int[] rectangle : rectangles) {
rectangle = map.get(rectangle);
}
int[][] g = new int;
for (int[] rectangle : rectangles) {
add(1, 1, 1, g);
add(1, rectangle + 1, -1, g);
add(rectangle + 1, 1, -1, g);
add(rectangle + 1, rectangle + 1, 1, g);
}
int[] ans = new int;
for (int i = 0; i < points.length; i++) {
ans = sum(points, points, g);
}
return ans;
}
private void add(int x, int y, int d, int[][] g) {
while (x < g.length) {
for (int j = y; j < g.length; j += lowbit(j)) {
g += d;
}
x += lowbit(x);
}
}
private int sum(int x, int y, int[][] g) {
int ans = 0;
while (x > 0) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans += g;
}
x -= lowbit(x);
}
return ans;
}
private int lowbit(int x) {
return x & (-x);
}
}
```
### 花期内花的数目
首先进行离散化处理，`start`, `end`, `person` 的原始数据范围都是 10^9, 实际上可以对他们进行压缩，也并不影响正确性。
比如 `[, ], ` 可以被压缩成 `[, ], `。
压缩后我们使用树状数组实现 “区间加、单点查” 的功能，即支持如下两种操作：
- 给区间 `` 加上 `d`
- 求点 `x` 的值
相当于使用树状数组维护 flowers 的差分数组的前缀和。
```java
class Solution {
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
TreeSet<Integer> numSet = new TreeSet<>();
for (int[] flower : flowers) {
numSet.add(flower);
numSet.add(flower);
}
for (int person : persons) {
numSet.add(person);
}
Map<Integer, Integer> numMap = new HashMap<>();
for (int num : numSet) {
numMap.put(num, numMap.size() + 1);
}
for (int[] flower : flowers) {
flower = numMap.get(flower);
flower = numMap.get(flower);
}
for (int i = 0; i < persons.length; i++) {
persons = numMap.get(persons);
}
// 区间加和，单点查询
int[] sum = new int;
for (int[] flower : flowers) {
add(sum, flower, 1);
add(sum, flower + 1, -1);
}
int[] res = new int;
for (int i = 0; i < persons.length; i++) {
res = sum(sum, persons);
}
return res;
}
private int sum(int[] sum, int x) {
int res = 0;
while (x > 0) {
res += sum;
x -= lowbit(x);
}
return res;
}
private void add(int[] sum, int x, int val) {
while (x < sum.length) {
sum += val;
x += lowbit(x);
}
}
private int lowbit(int x) {
return x & (-x);
}
}
页:
[1]