LCP 42. 玩具套圈 - Java 实现题目概述给定 toys[i] [xi, yi, ri]玩具坐标和半径和 circles[j] [xj, yj]套圈坐标所有套圈半径均为 r。求成功套中的玩具数量。套中条件套圈圆心到玩具圆心的距离 玩具半径 ≤ 套圈半径即\sqrt{(cx-tx)^2 (cy-ty)^2} tr \le r等价于圆心距不超过 r - tr。---核心思路哈希枚举直接暴力 O(|toys| \times |circles|) 会超时10^8 级别。关键观察题目约束 r \le 10tr \ge 1因此 r - tr \le 9。这意味着能套中某个玩具的套圈圆心只能分布在一个半径不超过 9 的极小圆内。由于坐标均为整数该圆内的整数点数量极其有限约 250 个。算法步骤1. 将所有套圈圆心编码后存入 HashSet2. 对每个玩具若 tr r 则直接跳过3. 枚举圆心偏移 (dx, dy)满足 dx^2 dy^2 \le (r-tr)^24. 检查 (txdx, tydy) 是否在套圈集合中时间复杂度 O(|toys| \cdot (r-tr)^2 |circles|)由于 r-tr \le 9实际运行极快。---Java 代码javaimport java.util.HashSet;import java.util.Set;class Solution {public int circleGame(int[][] toys, int[][] circles, int r) {// 用 HashSet 存储所有套圈圆心编码为 long 避免冲突// 编码方式x * UNIT yUNIT 需大于坐标最大范围final long UNIT 2_000_000_000L;SetLong circleSet new HashSet();for (int[] c : circles) {circleSet.add(c[0] * UNIT c[1]);}int ans 0;for (int[] toy : toys) {int tx toy[0], ty toy[1], tr toy[2];// 套圈半径小于玩具半径不可能套中if (tr r) {continue;}int diff r - tr; // 允许的最大圆心距int maxDisSq diff * diff; // 最大圆心距的平方boolean caught false;// 枚举所有可能的圆心偏移 (dx, dy)// 由于 diff 9最多枚举 (2*91)^2 361 个点for (int dx -diff; dx diff !caught; dx) {for (int dy -diff; dy diff !caught; dy) {// 剪枝只保留圆内的整数点if (dx * dx dy * dy maxDisSq) {continue;}long cx (long) tx dx;long cy (long) ty dy;if (circleSet.contains(cx * UNIT cy)) {caught true;}}}if (caught) {ans;}}return ans;}}---复杂度分析指标 复杂度 说明时间 O( circles空间 O( circles关键点说明- 编码技巧将二维坐标 (x, y) 编码为 x * UNIT y 存入 HashSet实现 O(1) 查询。UNIT 取 2 \times 10^9 可保证唯一性因坐标范围 \le 10^9。- 整数枚举利用 r \le 10 的强约束将几何问题转化为有限整数点枚举避免了浮点运算和复杂的空间索引结构。- 提前剪枝dx * dx dy * dy maxDisSq 跳过正方形四角外的点减少无效检查。