当前位置:网站首页>LeetCode_哈希表_困难_149. 直线上最多的点数
LeetCode_哈希表_困难_149. 直线上最多的点数
2022-07-05 20:57:00 【小城老街】
1.题目
给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1:
输入:points = [[1,1],[2,2],[3,3]]
输出:3
示例 2:
输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4
提示:
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points 中的所有点互不相同
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/max-points-on-a-line
2.思路
(1)暴力穷举法
暴力穷举法比较容易想到,由于在平面中两个不同的点可以确定一条直线,所以可以先穷举两个点的组合(即确定一条直线),然后再检查其余的点是否在该直线上。
(2)暴力穷举法改进_哈希表
思路参考该用户题解。
由于两点确定一条直线,所以可以先穷举所有可能出现的直线斜率(即枚举所有的点对),然后使用哈希表统计所有斜率对应的直线上点的数量(即键/值 = 斜率/点的数量),那么所有值中的最大值即为答案。
3.代码实现(Java)
//思路1————暴力穷举法
class Solution {
public int maxPoints(int[][] points) {
//最多有 cnt 个点在同一条直线上,由于 1 <= points.length <= 300,所以 cnt 的初始值为 1
int cnt = 1;
int n = points.length;
for (int i = 0; i < n; i++) {
int[] p1 = points[i];
for (int j = i + 1; j < n; j++) {
int[] p2 = points[j];
//p1 与 p2 一定在一条直线上,故至少有 2 个点在同一条直线上
int tmpCnt = 2;
for (int k = j + 1; k < n; k++) {
int[] p3 = points[k];
/* (1) 如果 (p1[1] - p2[1])/(p1[0] - p2[0]) == (p2[1] - p3[1])/(p2[0] - p3[0]) 那么 p1、p2、p3 这 3 个点在同一条直线上 (2) 为了防止整数相除时有精度损失,所以将上面的等式改为: (p1[0] - p2[0]) * (p2[1] - p3[1]) = (p1[1] - p2[1]) * (p2[0] - p3[0]) */
if ((p1[0] - p2[0]) * (p2[1] - p3[1]) == (p1[1] - p2[1]) * (p2[0] - p3[0])) {
tmpCnt++;
}
}
cnt = Math.max(tmpCnt, cnt);
}
}
return cnt;
}
}
//思路2————暴力穷举法改进_哈希表
class Solution {
public int maxPoints(int[][] ps) {
int n = ps.length;
int cnt = 1;
for (int i = 0; i < n; i++) {
Map<String, Integer> hashMap = new HashMap<>();
// 由当前点 i 发出的直线所经过的最多点数量
int max = 0;
for (int j = i + 1; j < n; j++) {
int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);
String key = (a / k) + "_" + (b / k);
hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
max = Math.max(max, hashMap.get(key));
}
cnt = Math.max(cnt, max + 1);
}
return cnt;
}
//求 a 和 b 的最大公约数
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
边栏推荐
- 当用户登录,经常会有实时的下拉框,例如,输入邮箱,将会@qq.com,@163.com,@sohu.com
- Abbkine BCA法 蛋白质定量试剂盒说明书
- Cutting edge technology for cultivating robot education creativity
- The development of research tourism practical education helps the development of cultural tourism industry
- Wanglaoji pharmaceutical's public welfare activity of "caring for the most lovely people under the scorching sun" was launched in Nanjing
- Return to blowing marshland -- travel notes of zhailidong, founder of duanzhitang
- Clion-MinGW编译后的exe文件添加ico图标
- Simple getting started example of Web Service
- MySQL fully parses json/ arrays
- 教你自己训练的pytorch模型转caffe(三)
猜你喜欢
Graph embedding learning notes
Analysis of steam education mode under the integration of five Education
Duchefa丨MS培养基含维生素说明书
PVC 塑料片BS 476-6 火焰传播性能测定
Abnova丨DNA 标记高质量控制测试方案
CADD course learning (7) -- Simulation of target and small molecule interaction (semi flexible docking autodock)
Écrire une interface basée sur flask
显示器要申请BS 476-7 怎么送样?跟显示屏一样吗??
线程池的使用
研學旅遊實踐教育的開展助力文旅產業發展
随机推荐
PHP deserialization +md5 collision
NPDP如何续证?操作指南来了!
水泥胶黏剂BS 476-4 不燃性测试
Abnova丨荧光染料 620-M 链霉亲和素方案
手机开户股票开户安全吗?我家比较偏远,有更好的开户途径么?
基於flask寫一個接口
Monorepo management methodology and dependency security
挖财商学院给的证券账户安全吗?可以开户吗?
Enclosed please find. Net Maui's latest learning resources
中国管理科学研究院凝聚行业专家,傅强荣获智库专家“十佳青年”称号
Monorepo管理方法论和依赖安全
浅聊我和一些编程语言的缘分
leetcode:1755. 最接近目标值的子序列和
LeetCode: Distinct Subsequences [115]
ProSci LAG-3 重组蛋白说明书
Écrire une interface basée sur flask
木板ISO 5660-1 热量释放速率摸底测试
Who the final say whether the product is good or not? Sonar puts forward performance indicators for analysis to help you easily judge product performance and performance
When steam education enters personalized information technology courses
Maker education infiltrating the transformation of maker spirit and culture