- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现LeetCode(149.共线点个数)由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 。
Example 1
Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4 。
Example 2
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6 。
这道题给了我们一堆二维点,然后让求最大的共线点的个数,根据初中数学可以知道,两点确定一条直线,而且可以写成 y = ax + b 的形式,所有共线的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率,每个斜率代表一条直线,对每一条直线,带入所有的点看是否共线并计算个数,这是整体的思路。但是还有两点特殊情况需要考虑,一是当两个点重合时,无法确定一条直线,但这也是共线的情况,需要特殊处理。二是斜率不存在的情况,由于两个点 (x1, y1) 和 (x2, y2) 的斜率k表示为 (y2 - y1) / (x2 - x1),那么当 x1 = x2 时斜率不存在,这种共线情况需要特殊处理。这里需要用到 TreeMap 来记录斜率和共线点个数之间的映射,其中第一种重合点的情况假定其斜率为 INT_MIN,第二种情况假定其斜率为 INT_MAX,这样都可以用 TreeMap 映射了。还需要顶一个变量 duplicate 来记录重合点的个数,最后只需和 TreeMap 中的数字相加即为共线点的总数,但这种方法现在已经无法通过 OJ 了,代码可以参见评论区八楼.
由于通过斜率来判断共线需要用到除法,而用 double 表示的双精度小数在有的系统里不一定准确,为了更加精确无误的计算共线,应当避免除法,从而避免无线不循环小数的出现,那么怎么办呢,这里把除数和被除数都保存下来,不做除法,但是要让这两数分别除以它们的最大公约数,这样例如8和4,4和2,2和1,这三组商相同的数就都会存到一个映射里面,同样也能实现目标,而求 GCD 的函数如果用递归来写那么一行就搞定了,叼不叼,这个方法能很好的避免除法的出现,算是牺牲了空间来保证精度吧,参见代码如下:
C++ 解法一:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class
Solution {
public
:
int
maxPoints(vector<vector<
int
>>& points) {
int
res = 0;
for
(
int
i = 0; i < points.size(); ++i) {
map<pair<
int
,
int
>,
int
> m;
int
duplicate = 1;
for
(
int
j = i + 1; j < points.size(); ++j) {
if
(points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
++duplicate;
continue
;
}
int
dx = points[j][0] - points[i][0];
int
dy = points[j][1] - points[i][1];
int
d = gcd(dx, dy);
++m[{dx / d, dy / d}];
}
res = max(res, duplicate);
for
(auto it = m.begin(); it != m.end(); ++it) {
res = max(res, it->second + duplicate);
}
}
return
res;
}
int
gcd(
int
a,
int
b) {
return
(b == 0) ? a : gcd(b, a % b);
}
};
|
Java 解法一:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class
Solution {
public
int
maxPoints(
int
[][] points) {
int
res =
0
;
for
(
int
i =
0
; i < points.length; ++i) {
Map<Map<Integer, Integer>, Integer> m =
new
HashMap<>();
int
duplicate =
1
;
for
(
int
j = i +
1
; j < points.length; ++j) {
if
(points[i][
0
] == points[j][
0
] && points[i][
1
] == points[j][
1
]) {
++duplicate;
continue
;
}
int
dx = points[j][
0
] - points[i][
0
];
int
dy = points[j][
1
] - points[i][
1
];
int
d = gcd(dx, dy);
Map<Integer, Integer> t =
new
HashMap<>();
t.put(dx / d, dy / d);
m.put(t, m.getOrDefault(t,
0
) +
1
);
}
res = Math.max(res, duplicate);
for
(Map.Entry<Map<Integer, Integer>, Integer> e : m.entrySet()) {
res = Math.max(res, e.getValue() + duplicate);
}
}
return
res;
}
public
int
gcd(
int
a,
int
b) {
return
(b ==
0
) ? a : gcd(b, a % b);
}
}
|
令博主惊奇的是,这道题的 OJ 居然容忍 brute force 的方法通过,博主认为下面这种 O(n3) 的解法之所以能通过 OJ,可能还有一个原因就是用了比较高效的判断三点共线的方法。一般来说判断三点共线有三种方法,斜率法,周长法,面积法 。而其中通过判断叉积为零的面积法是坠好的。比如说有三个点 A(x1, y1)、B(x2, y2)、C(x3, y3),那么判断三点共线就是判断下面这个等式是否成立:
行列式的求法不用多说吧,不会的话回去翻线性代数,当初少打点刀塔不就好啦~ 。
C++ 解法二:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class
Solution {
public
:
int
maxPoints(vector<vector<
int
>>& points) {
int
res = 0;
for
(
int
i = 0; i < points.size(); ++i) {
int
duplicate = 1;
for
(
int
j = i + 1; j < points.size(); ++j) {
int
cnt = 0;
long
long
x1 = points[i][0], y1 = points[i][1];
long
long
x2 = points[j][0], y2 = points[j][1];
if
(x1 == x2 && y1 == y2) {++duplicate;
continue
;}
for
(
int
k = 0; k < points.size(); ++k) {
int
x3 = points[k][0], y3 = points[k][1];
if
(x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {
++cnt;
}
}
res = max(res, cnt);
}
res = max(res, duplicate);
}
return
res;
}
};
|
Java 解法二:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class
Solution {
public
int
maxPoints(
int
[][] points) {
int
res =
0
, n = points.length;
for
(
int
i =
0
; i < n; ++i) {
int
duplicate =
1
;
for
(
int
j = i +
1
; j < n; ++j) {
int
cnt =
0
;
long
x1 = points[i][
0
], y1 = points[i][
1
];
long
x2 = points[j][
0
], y2 = points[j][
1
];
if
(x1 == x2 && y1 == y2) {++duplicate;
continue
;}
for
(
int
k =
0
; k < n; ++k) {
int
x3 = points[k][
0
], y3 = points[k][
1
];
if
(x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 ==
0
) {
++cnt;
}
}
res = Math.max(res, cnt);
}
res = Math.max(res, duplicate);
}
return
res;
}
}
|
Github 同步地址:
https://github.com/grandyang/leetcode/issues/149 。
类似题目:
Line Reflection 。
参考资料:
https://leetcode.com/problems/max-points-on-a-line/ 。
https://leetcode.com/problems/max-points-on-a-line/discuss/221044/ 。
https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes 。
https://leetcode.com/problems/max-points-on-a-line/discuss/47117/Sharing-my-simple-solution-with-explanation 。
到此这篇关于C++实现LeetCode(149.共线点个数)的文章就介绍到这了,更多相关C++实现共线点个数内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我! 。
原文链接:https://www.cnblogs.com/grandyang/p/4579693.html 。
最后此篇关于C++实现LeetCode(149.共线点个数)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(149.共线点个数)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我创建了一个 View (称为 masterView),CGRect 的 x=160、y=186、width=1600、height=380。该 View 包含 5 个 subview ,每个 sub
我是 R 的新手,目前正在处理边缘列表形式的协作数据,该列表具有 32 列和大约 200.000 行。我想根据国家之间的相互作用创建一个(共)现矩阵。但是,我想通过对象的总数来计算交互次数。 期望结果
考虑以下发展: Require Import Relation RelationClasses. Set Implicit Arguments. CoInductive stream (A : Typ
我正在玩弄这种语言来开始学习,我对递归定义的工作原理感到困惑。 例如,让我们采用三角形数的序列(TN n = sum [1..n]) 提供的解决方案是: triangularNumbers = sca
我正在尝试获取“总分钟数”值中的 PHP“DateInterval”值。如何获得?似乎简单格式(“%i 分钟”)不起作用? 示例代码如下: $test = new \DateTime("48 hour
我有这个脚本可以通过电子邮件自动发送负载信息: if(confirm('', 'Are you sure?') == true) { // enviar mails var emails = new
我有一些数据要查询。该表由两列组成 - 一个唯一 ID 和一个值。我想计算每个唯一值出现的次数(这可以通过 COUNT 和 GROUP BY 轻松完成),但我希望能够对其进行计数。所以,我想看看有多少
当我在我的 Java 代码上运行 PMD 时,它显示的错误消息之一是“类 STWeb 具有 20 的圈复杂度”。通常我的java类是这样的 public class STWeb implements
尝试在打印时在页面底部显示第 1 页,共 10 页... 第 1 页,共 0 页 正在显示,因此计数器(页面)似乎无法正常工作。我正在使用 Chrome,所以 @pages { ... 也不起作用。有
我在尝试运行单元测试用例时收到 Executed 0 of 0 ERROR 错误。我遵循了针对此问题提到的几个解决方案,但我仍然遇到相同的错误。 尝试过: 删除 angular-scenario 文件
我们有一个应用程序,可以在运行时生成大约 100 个动画,并将它们全部添加到单个 Storyboard 中然后播放。问题是动画速度非常慢。进行动画处理的对象是形状和样条线,并且在后端完成大量计算以生成
我正在为数学演示编写凯撒加密代码。今天,我一直在为我的演讲编写代码。早上这个代码就开始工作了。但现在在学校,我遇到了一个异常(exception),我认为 for 超出了我的符号表的长度。 异常(ex
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 6 年前。 Improve th
我有一张带有 4 个标签的表格,效果很好。当我使用也能正常工作的搜索栏时,表格只显示两个标签: - (void)viewDidLoad { [super viewDidLoad]; NSS
我正在使用 iText 在我的 Java EE 应用程序中生成 PDF 文档。 PDF 文件的编码驻留在 JSP 中。 我想在每个页脚中实现以下页面格式, REF:XXXXXXX 第 X 页,共第 Y
我试图找出(出于好奇)哪个线程实际调用了单例构造函数。好吧,我完全理解每次执行测试程序时线程都会不同,只是想在实用上检查是否相同。我试过 dumpStack() printStackTrace() g
我在工作时遇到了一些麻烦。这可能真的很简单,但我让它变得比可能的更困难。所以我有一个包含 3 组 UL 的 div。 代码如下: content here content here c
我有一个问题,当网格为空时,为什么它显示 Page 1 of 0 不能是 Page 1 of 1 或更合理的东西吗? 我的代码 var xml=client.responseText;
我想将 Crashlytics 添加到我的项目中,我根据 Fabric Mac 应用程序制作了所有内容,现在我停留在 Step 2 of 2 when verifying installation 我
我正在使用 qt 从 html 代码生成一个 pdf 文件: QTextDocument *document = new QTextDocument(); document->setHtml(html
我是一名优秀的程序员,十分优秀!