作者推荐
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
本文涉及的基础知识点
优化后，就不需要二分了。
题目
「力扣挑战赛」场地外，小力组织了一个套玩具的游戏。所有的玩具摆在平地上，toys[i] 以 [xi,yi,ri] 的形式记录了第 i 个玩具的坐标 (xi,yi) 和半径 ri。小扣试玩了一下，他扔了若干个半径均为 r 的圈，circles[j] 记录了第 j 个圈的坐标 (xj,yj)。套圈的规则如下：
若一个玩具被某个圈完整覆盖了（即玩具的任意部分均在圈内或者圈上），则该玩具被套中。
若一个玩具被多个圈同时套中，最终仅计算为套中一个玩具
请帮助小扣计算，他成功套中了多少玩具。
注意：
输入数据保证任意两个玩具的圆心不会重合，但玩具之间可能存在重叠。
示例 1：
输入：toys = [[3,3,1],[3,2,1]], circles = [[4,3]], r = 2
输出：1
解释： 如图所示，仅套中一个玩具
示例 2：
输入：toys = [[1,3,2],[4,3,1],[7,1,2]], circles = [[1,0],[3,3]], r = 4
输出：2
解释： 如图所示，套中两个玩具image.png
参数范围：
1 <= toys.length <= 104
0 <= toys[i][0], toys[i][1] <= 109
1 <= circles.length <= 104
0 <= circles[i][0], circles[i][1] <= 109
1 <= toys[i][2], r <= 10
分析
圆的关系
圆和圆的关系分以下几种：
| 相离 | 圆心距离大于半径之和 | 没套中 |
| 外切 | 圆新距离等与半径和 | 没套中 |
| 相交 | 圆心距在(半径差，半径和) | 没套中 |
| 内切 | 圆心距等于半径之差 | 套中 |
| 内含 | 圆心距小于半径之差 | 套中 |
| 重合 | 心距等于半径之差 | 套中 |
套中的条件：圆心距小于等于半径之差。注意:套的半径必须大于等于玩具。
枚举什么
枚举玩具和套，时间复杂度O(108)，超时。可以枚举玩具和套的中心，这样复杂度就降到o(10^6)。
变量
| setCircleRC | 所有套的中心,中心相同的套忽略 |
| vPoints | 假定玩具中心在(0,0)，套中心在那儿，可以包括玩具中心 |
代码
核心代码
class Solution { public: int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) { unordered_set<long long> setCircleRC; for (const auto& v : circles) { setCircleRC.emplace(v[0]* m_llUnit +v[1]); } vector<pair<int, int>> vPoints; for (int x = -r; x <= r; x++) { for (int y = -r; y <= r; y++) { if (x * x + y * y <= r * r) { vPoints.emplace_back(x, y); } } } int iRet = 0; for (const auto& v : toys) { if (v[2] > r) { continue; } bool is = false; for (const auto& [x, y] : vPoints) { const int iDis2 = x * x + y * y; if (iDis2 > (r - v[2]) * (r - v[2])) { continue; } is |= setCircleRC.count((v[0]+x) * m_llUnit + (v[1]+y)); } iRet += is; } return iRet; } const long long m_llUnit = 10'000'000'000; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<vector<int>> toys, circles; int r; { Solution slu; toys = { {3,3,1},{3,2,1} }, circles = { {4,3} }, r = 2; auto res = slu.circleGame(toys,circles,r); Assert(1, res); } { Solution slu; toys = { {1,3,2},{4,3,1},{7,1,2} }, circles = { {1,0},{3,3} }, r = 4; auto res = slu.circleGame(toys, circles, r); Assert(2, res); } }
2023年3月
class Solution { public: int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) { std::unordered_set<long long> mCircleXY; for (const auto& v : circles) { mCircleXY.insert(m_llMul*v[0] + v[1]); } int iRet = 0; for (const auto& toy : toys) { if (toy[2] > r) { continue; } long long iMaxDis2 = (long long)(r - toy[2])*(r - toy[2]); int iMaxDis = sqrt(iMaxDis2) + 0.5; bool bCan = false; for (int x = toy[0] - iMaxDis; x <= toy[0] + iMaxDis; x++) { for (int y = toy[1] - iMaxDis; y <= toy[1] + iMaxDis; y++) { const long long iCurDis2 = (long long)(x - toy[0])*(x - toy[0]) + (long long)(y - toy[1])*(y - toy[1]); if (iCurDis2 > iMaxDis2) { continue; } const long long llMask = m_llMul*x + y; if (mCircleXY.count(llMask)) { bCan = true; break; } } if (bCan) { break; } } if (bCan) { iRet++; } } return iRet; } const long long m_llMul = 1000 * 1000 * 1000 * 2; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
