上岸算法 | LeetCode Weekly Contest 第 290 场周赛解题报告

上岸算法 · 发表于 2022-4-23 23:29:54

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

### 多个数组求交集

使用 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[0]);
      for (int i = 1; i < nums.length; i++) {
         list = intersection(list, toList(nums[i]));
      }
      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[0];
         int y = circle[1];
         int r = circle[2];
         // 出于便利，直接枚举正方形区域，然后判断是否在圆内
         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[0]);
      }
      for (int[] rectangle : rectangles) {
         xs.add(rectangle[0]);
      }
      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[0] = map.get(point[0]);
      }
      for (int[] rectangle : rectangles) {
         rectangle[0] = map.get(rectangle[0]);
      }
      int[][] g = new int[100005][105];
      for (int[] rectangle : rectangles) {
         add(1, 1, 1, g);
         add(1, rectangle[1] + 1, -1, g);
         add(rectangle[0] + 1, 1, -1, g);
         add(rectangle[0] + 1, rectangle[1] + 1, 1, g);
      }
      int[] ans = new int[points.length];
      for (int i = 0; i < points.length; i++) {
         ans[i] = sum(points[i][0], points[i][1], g);
      }
      return ans;
}

private void add(int x, int y, int d, int[][] g) {
      while (x < g.length) {
         for (int j = y; j < g[0].length; j += lowbit(j)) {
            g[x][j] += 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][j];
         }
         x -= lowbit(x);
      }
      return ans;
}

private int lowbit(int x) {
      return x & (-x);
}
}
```

### 花期内花的数目

首先进行离散化处理，`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 的差分数组的前缀和。

```java
class Solution {
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
      TreeSet<Integer> numSet = new TreeSet<>();
      for (int[] flower : flowers) {
         numSet.add(flower[0]);
         numSet.add(flower[1]);
      }
      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[0] = numMap.get(flower[0]);
         flower[1] = numMap.get(flower[1]);
      }
      for (int i = 0; i < persons.length; i++) {
         persons[i] = numMap.get(persons[i]);
      }
      // 区间加和，单点查询
      int[] sum = new int[numMap.size() + 5];
      for (int[] flower : flowers) {
         add(sum, flower[0], 1);
         add(sum, flower[1] + 1, -1);
      }
      int[] res = new int[persons.length];
      for (int i = 0; i < persons.length; i++) {
         res[i] = sum(sum, persons[i]);
      }
      return res;
}

private int sum(int[] sum, int x) {
      int res = 0;
      while (x > 0) {
         res += sum[x];
         x -= lowbit(x);
      }
      return res;
}

private void add(int[] sum, int x, int val) {
      while (x < sum.length) {
         sum[x] += val;
         x += lowbit(x);
      }
}

private int lowbit(int x) {
      return x & (-x);
}
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法 | LeetCode Weekly Contest 第 290 场周赛解题报告

登录后可回复主题