玩具套圈
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 288 ms, 内存: 36.2 MB
/*
* 思路:
* 使用Java Stream API实现同样的逻辑。
* 对于每个玩具,检查它是否在任意一个圈内。
* 计算玩具中心到圈中心的距离,如果距离加上玩具半径小于等于圈的半径,则玩具被套中。
* 如果一个玩具被多个圈套中,只计数一次。
*/
import java.util.*;
import java.util.stream.*;
public class ToyCircleGameStream {
public int countCoveredToys(int[][] toys, int[][] circles, int r) {
return (int) IntStream.range(0, toys.length)
.filter(i -> Arrays.stream(circles)
.anyMatch(circle -> {
double distance = Math.sqrt(Math.pow(toys[i][0] - circle[0], 2) + Math.pow(toys[i][1] - circle[1], 2));
return distance + toys[i][2] <= r;
}))
.distinct()
.count();
}
public static void main(String[] args) {
ToyCircleGameStream game = new ToyCircleGameStream();
int[][] toys1 = {{3, 3, 1}, {3, 2, 1}};
int[][] circles1 = {{4, 3}};
int r1 = 2;
System.out.println(game.countCoveredToys(toys1, circles1, r1)); // 输出:1
int[][] toys2 = {{1, 3, 2}, {4, 3, 1}, {7, 1, 2}};
int[][] circles2 = {{1, 0}, {3, 3}};
int r2 = 4;
System.out.println(game.countCoveredToys(toys2, circles2, r2)); // 输出:2
}
}
解释
方法:
此题解采用迭代+排序+二分搜索的方法来确定玩具是否被套圈。首先,对所有的圈按照x坐标进行排序,并为每个x坐标建立一个列表,存储对应的y坐标。对于每个玩具,根据其位置和大小计算出可能套中该玩具的圈的潜在x和y坐标范围。接着,对每个玩具遍历这个范围内的所有潜在圈的坐标,使用二分搜索确定潜在的y坐标。若计算得出的圈心到玩具心的距离小于或等于圈半径减去玩具半径的平方,则该玩具被套中。
时间复杂度:
O(n + Cm)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么题解中选择对圈的x坐标进行排序,而不是y坐标或两者同时排序?
▷🦆
排序圈后,你是如何决定使用字典来存储每个x坐标下的y坐标列表的?这种数据结构有什么优势?
▷🦆
在计算玩具是否被套圈时,`d = r - ri` 如果结果为负,直接返回False。这里的逻辑是否意味着只有当圈的半径大于或等于玩具半径时,玩具才可能被套中?
▷