leetcode
leetcode 3001 ~ 3050
玩具套圈

玩具套圈

难度:

标签:

题目描述

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坐标进行排序是因为这样可以根据玩具的x坐标快速地定位可能与玩具相交的圈的潜在范围。通过排序x坐标,我们可以利用二分搜索快速缩小圈的搜索范围,从而减少不必要的检查。如果同时对x和y坐标排序,则会增加处理排序后数据的复杂性,因为我们需要同时考虑二维上的位置关系,这可能导致效率降低。因此,单独对x坐标进行排序并结合y坐标的列表,是一个在效率和实现复杂度之间较好的折中。
🦆
排序圈后,你是如何决定使用字典来存储每个x坐标下的y坐标列表的?这种数据结构有什么优势?
在排序圈的x坐标后,使用字典来存储每个x坐标对应的y坐标列表是为了快速访问和检索特定x坐标下所有可能的y坐标。这种数据结构的优势在于它提供了快速的查找时间和灵活的数据访问。对于每个特定的x坐标,我们可以直接通过字典访问所有相关的y坐标,而不需要遍历整个圈的列表。这样可以显著提高查询效率,尤其是在处理大量数据时。此外,字典的使用也支持动态插入和删除操作,这在处理变动的数据集时非常有用。
🦆
在计算玩具是否被套圈时,`d = r - ri` 如果结果为负,直接返回False。这里的逻辑是否意味着只有当圈的半径大于或等于玩具半径时,玩具才可能被套中?
是的,这里的逻辑正是意味着只有当圈的半径大于或等于玩具的半径时,玩具才可能被套中。这是因为如果圈的半径小于玩具的半径,即使圈的中心点正好位于玩具的中心点上,圈也无法完全覆盖玩具。因此,只有当圈的半径不小于玩具的半径时,我们才继续计算圈心到玩具心的距离是否小于或等于调整后的圈半径的平方(即 `d^2`),以判断玩具是否被套中。

相关问题