【力扣LCR42题解析】套圈游戏:用距离平方优化算法解题

文章封面

截图未命名

一、题目解读

力扣LCR42题“圆圈游戏”要求计算给定玩具集合中,能被套圈覆盖的玩具数量。每个玩具和套圈均由坐标及半径定义,需判断玩具是否在套圈覆盖范围内。题目核心在于高效计算点与圆的位置关系,并统计符合条件的结果。

二、解题思路

采用“半径预筛选+距离平方判定”策略:

  1. 过滤无效玩具:优先排除半径大于套圈半径的玩具(因不可能被覆盖)。

  2. 逐点验证覆盖:对剩余玩具,遍历所有套圈计算其与圆心距离平方,利用平方避免开方运算,通过比较距离平方与半径差平方判断是否覆盖。

  3. 优化计算逻辑:通过提前终止(找到覆盖即break)减少冗余遍历。

三、解题步骤

  1. 初始化计数器:count记录被覆盖玩具数量。

  2. 外层循环:遍历玩具列表,解析坐标与半径(tx, ty, tr)。

  3. 半径过滤:若tr > r(玩具半径大于套圈半径),跳过当前玩具。

  4. 内层循环:遍历套圈列表,计算玩具与套圈圆心距离平方(dx^2 + dy^2)。

  5. 覆盖判定:若距离平方小于半径差平方(r - tr)^2,标记覆盖并跳出内层循环。

  6. 统计结果:若玩具被覆盖,计数器递增。

  7. 返回最终数量。

四、代码与注释

#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) {
        int count = 0; // 初始化覆盖计数
        for (const auto& toy : toys) { // 遍历玩具
            int tx = toy[0], ty = toy[1], tr = toy[2];
            // 玩具半径必须小于等于套圈半径才可能被套住
            if (tr > r) continue;

            bool covered = false; // 标记是否被覆盖
            for (const auto& circle : circles) {
                int cx = circle[0], cy = circle[1];
                // 计算两点间距离平方(避免浮点运算)
                long dx = tx - cx, dy = ty - cy;
                long distance_sq = dx * dx + dy * dy;
                long max_distance = r - tr; // 允许最大距离平方
                // 比较距离平方与半径平方差
                if (distance_sq <= max_distance * max_distance) {
                    covered = true;
                    break; // 找到覆盖即终止
                }
            }
            if (covered) count++;
        }
        return count;
    }
};

五、总结

本解法通过半径预筛选降低无效计算,结合距离平方判定避免浮点误差,通过提前终止循环优化时间复杂度。核心在于将几何问题转化为代数比较,兼顾效率与准确性。适用于处理大量坐标与半径的覆盖判定场景。

来源:力扣题解

评论

暂无评论