LeetCode 1453:圆形省道板内的最大省道数
LeetCode 1453:圆形省道板内的最大省道数
提问于 2020-07-21 22:04:22
我发布了一个LeetCode问题的代码。如果你想复习，请这样做。谢谢您抽时间见我!
问题
墙上有一个很大的方形墙和一个圆形的飞镖板。你被要求把飞镖扔进蒙着眼睛的板子里。掷向墙上的飞镖表示为二维平面上的一系列点。
返回半径为r的任意圆刻度板内或位于其上的最大点数。
示例1:
Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.示例2:
Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).示例3:
Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1示例4:
Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4Constraints:
输入
[[-2,0],[2,0],[0,2],[0,-2]]
2
[[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]
5
[[-2,0],[2,0],[0,2],[0,-2]]
1
[[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]]
2
[[5738,-1857],[2264,1769],[5944,-9368],[3459,-9748],[8624,159],[985,-5051],[-8275,-9383],[7923,-591],[-8121,4781],[-9594,938],[-24,223],[9084,-4952],[-6787,5289],[4879,-4],[3998,369],[-7996,-7220],[-414,3638],[5092,4406],[1454,2965],[9210,-6966],[-4111,-8614],[4507,2213],[-4112,3699],[-9956,-2420],[7246,6775],[1164,5762],[6778,-5099],[-6655,-9514],[-2778,-7768],[6973,-7458],[7334,-1124],[4840,-8991],[941,5018],[1937,3608],[6807,6159],[763,1355],[-9776,-5074],[1107,1822],[-6779,-5400],[4219,-5674],[9823,-4630],[-9172,-7089],[-1875,162],[2267,1685],[4161,-1638],[-2475,9697],[-5367,-952],[-7786,4367],[839,1415],[8832,-4596],[-3843,7126],[-4242,8513],[-7883,1951],[9105,8342],[-4109,-4510],[1875,3149],[-7759,-6505],[1764,1624],[-6917,-6653],[-1438,6916],[-758,-3300],[3694,6699],[6135,2622],[7485,8284],[-9616,-8501],[408,4743],[8939,-731],[9208,-3748],[6059,-2587],[8403,4154],[2361,5708],[-3958,-3943],[-1746,-9082],[2864,-3231],[-4940,8519],[-8786,7898],[5154,-3647],[9011,8170],[-205,8717],[...
4411输出
4
5
1
4
23码
#include <cstdint>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
class Solution {
static constexpr double precision = 1e-6;
double R;
static struct Point {
double x;
double y;
};
std::vector<Point> point;
public:
std::int_fast32_t numPoints(
const std::vector<std::vector<int>>& points,
const std::int_fast32_t r
) {
const std::size_t length = points.size();
R = (double) r;
point.resize(length);
for (std::size_t len = 0; len < length; ++len) {
point[len].x = points[len][0];
point[len].y = points[len][1];
}
std::int_fast32_t max_darts = 1;
for (std::size_t i = 0; i < length; ++i) {
for (std::size_t j = 0; j < length; ++j) {
if (i == j || getEuclideanDistance(point[i], point[j]) - 2 * R > precision) {
continue;
}
std::int_fast32_t curr_darts = 0;
const auto center = getDartboardCenter(point[i], point[j]);
for (std::size_t k = 0; k < length; ++k) {
if (getEuclideanDistance(point[k], center.first) - R < precision) {
++curr_darts;
}
}
max_darts = std::max(max_darts, curr_darts);
}
}
return max_darts;
}
private:
double getEuclideanDistance(
const Point& a,
const Point& b
) {
return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2));
}
std::pair<Point, Point> getDartboardCenter(
const Point& a,
const Point& b
) {
Point mid;
std::pair<Point, Point> center;
mid.x = (a.x + b.x) / 2;
mid.y = (a.y + b.y) / 2;
const double theta = std::atan2(a.y - b.y, b.x - a.x);
const double temp_point = getEuclideanDistance(a, b) / 2;
const double euc_dist = std::sqrt(std::pow(R, 2) - std::pow(temp_point, 2));
center.first.x = mid.x - euc_dist * std::sin(theta);
center.first.y = mid.y - euc_dist * std::cos(theta);
// For optimization, later!
center.second.x = mid.x + euc_dist * std::sin(theta);
center.second.y = mid.y + euc_dist * std::cos(theta);
return center;
}
};参考资料
回答 1
Code Review用户
回答已采纳
发布于 2020-07-21 22:51:34
不更改API
LeetCode问题提供了公共API：
int numPoints(vector<vector<int>>& points, int r)不要将int更改为int_fast32_t，因为这可能会导致您的函数与LeetCode所期望的不兼容。如果您想在内部使用int_fast32_t，那很好。
使函数不访问成员变量static
这适用于getEuclideanDistance()。
使函数不更改成员变量const
这适用于getDartboardCenter()。
命名事物
这是计算机科学中的两大难题之一，同时也是缓存失效和错误对错之一。
您的函数getDartboardCenter()实际上不返回省道板的中心。它只返回基于两个输入点的两个猜测。只有一对的元素被使用过。也许getCandidateCenter()是个更好的名字。
另外，temp_point不是一个点，它是一个距离，所以将其命名为temp_distance或temp_dist。
使用std::hypot()
标准库已经为您提供了一个函数，可以帮助您计算欧几里得距离：std::hypot()。所以：
static double getEuclideanDistance(const Point& a, const Point& b) {
return std::hypot(a.x - b.x, a.y - b.y);
}但更好的是：
避免不必要的浮点数学
你已经注意到浮点数学不是无限精确的。但是，整数数学是(只要不超过整数变量所能容纳的最大值)。您可以通过以下方式检查具有整数坐标的给定点是否位于以半径为R的原点的圆心内：
int R; // radius
int x, y; // point coordinates
if (x * x + y * y <= R * R) {
// point x, y is inside the circle
}可能还有更多的数学可以用整数来完成。
简化了三角
有两个双打，dx和dy，和：
double theta = std::atan2(dy, dx);
double dist = std::hypot(dy, dx);然后是std::sin(theta) * dist == dy和std::cos(theta) * dist == dx。这意味着您根本不需要使用这些三角函数，并且可以编写：
const double temp_dist = getEuclideanDistance(a, b);
const double euc_dist = std::sqrt(std::pow(R, 2) - std::pow(temp_dist / 2, 2));
const double scaled_dist = euc_dist / temp_dist;
center.first.x = mid.x - scaled_dist * a;
center.first.y = mid.y - scaled_dist * b;这可以进一步简化一些。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/245840
复制相关文章
相似问题
腾讯云开发者
