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

贾蔷
• 阅读 24

【力扣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;
    }
};

五、总结

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

来源:力扣题解

点赞
收藏
评论区
推荐文章
贾蔷 贾蔷
1个月前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
贾蔷 贾蔷
1个月前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
贾蔷 贾蔷
1个月前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
1个月前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
2星期前
NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解
一、题目解读问题(,)要求使用给定数量的火柴棒,构造形如ABC的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式数量。题目核心在于将数字拆解与火柴棒消耗建模为数学问题,寻找高效解法。二、解题思路采用火柴棒计数策略:1.关系
贾蔷 贾蔷
2星期前
洛谷1220题解:动态规划与区间DP优化解法
一、题目解读1220题要求计算在n个位置放置灯的情况下,通过关闭连续区间灯并移动至区间端点,使得总耗电量最小。需考虑灯的功率与位置差异,设计高效的求解最优策略。二、解题思路1.:定义状态dp:使用sum存储灯功率前缀和,简化区间电量计算。3.核心:○向左
深度学习 深度学习
2星期前
2015年蓝桥杯国赛C组机器人繁殖题解析:高精度整数代码实现与解题思路
一、题目解读2015年C组“机器人繁殖”问题要求求解机器人按月繁殖的累计数量。题目设定初始机器人数量为a,每月新增b台,需计算n个月后总机器人数。由于繁殖数量可能呈指数级增长,普通整数类型无法存储结果,因此需采用高精度整数运算解决。二、解题思路核心在于自定
贾蔷 贾蔷
1星期前
洛谷P1102题解:利用哈希表优化的数对统计 C++代码解析
一、题目解读P1102题要求处理一组整数与常数C,统计数组中是否存在元素A与B满足ABC。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。二、解题思路采用(unorderedmap)实现高效统计。首先遍
深度学习 深度学习
1天前
洛谷P2758题解:动态规划求解编辑距离的完整攻略
一、题目解读P2758题要求计算两个之间的编辑距离,即通过插入、删除、替换三种操作将字符串A转换为B所需的最小操作次数。题目考察的核心是在中的应用,需要找到最优的路径。二、解题思路采用(DynamicProgramming)策略。核心思想是构建二维dp,d
贾蔷 贾蔷
1天前
(2017蓝桥杯省A)洛谷P8650题解:递归解析正则表达式并求解最大长度
一、题目解读P8650题要求解析由‘x’、‘|’和括号组成的表达式,计算并输出其最大长度。题目核心在于处理嵌套括号与‘|’分隔的项。二、解题思路使用策略:1.解析因子:识别单个‘x’或括号表达式,递归处理括号内内容,累加长度。2.解析项:通过‘|’分隔,递