当前位置:网站首页>LeetCode_ Hash table_ Difficulties_ 149. Maximum number of points on the line
LeetCode_ Hash table_ Difficulties_ 149. Maximum number of points on the line
2022-07-05 20:58:00 【Old street of small town】
1. subject
Give you an array points , among points[i] = [xi, yi] Express X-Y A point on the plane . Find out how many points are in the same line at most .
Example 1:
Input :points = [[1,1],[2,2],[3,3]]
Output :3
Example 2:
Input :points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output :4
Tips :
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points All points in are different from each other
source : Power button (LeetCode)
link :https://leetcode.cn/problems/max-points-on-a-line
2. Ideas
(1) The law of violent exhaustion
Violent exhaustion is easier to think of , Because two different points in the plane can determine a straight line , So you can First enumerate the combination of two points ( That is to determine a straight line ), Then check whether the remaining points are on the straight line .
(2) Improvement of violent exhaustion _ Hashtable
Train of thought reference The user's question solution .
Because two points determine a straight line , So we can enumerate all the possible slope of the straight line ( That is, enumerate all point pairs ), Then use the hash table to count the number of points on the straight line corresponding to all slopes ( Instant key / value = Slope / The number of points ), Then the maximum of all values is the answer .
3. Code implementation (Java)
// Ideas 1———— The law of violent exhaustion
class Solution {
public int maxPoints(int[][] points) {
// At most cnt The points are on the same straight line , because 1 <= points.length <= 300, therefore cnt The initial value of 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 And p2 It must be in a straight line , So at least 2 The points are on the same straight line
int tmpCnt = 2;
for (int k = j + 1; k < n; k++) {
int[] p3 = points[k];
/* (1) If (p1[1] - p2[1])/(p1[0] - p2[0]) == (p2[1] - p3[1])/(p2[0] - p3[0]) that p1、p2、p3 this 3 The points are on the same straight line (2) In order to prevent the loss of accuracy when dividing integers , So change the above equation to : (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;
}
}
// Ideas 2———— Improvement of violent exhaustion _ Hashtable
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<>();
// From the current point i The maximum number of points passed by the emitted straight line
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;
}
// seek a and b Maximum common divisor of
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
边栏推荐
- 《SAS编程和数据挖掘商业案例》学习笔记# 19
- 教你自己训练的pytorch模型转caffe(三)
- ts 之 属性的修饰符public、private、protect
- Abnova DNA marker high quality control test program
- 显示器要申请BS 476-7 怎么送样?跟显示屏一样吗??
- 2.<tag-哈希表, 字符串>补充: 剑指 Offer 50. 第一个只出现一次的字符 dbc
- 序列联配Sequence Alignment
- Popular science | does poor English affect the NPDP exam?
- poj 3414 Pots (bfs+线索)
- Cutting edge technology for cultivating robot education creativity
猜你喜欢
渗透创客精神文化转化的创客教育
MySQL fully parses json/ arrays
珍爱网微服务底层框架演进从开源组件封装到自研
木板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
Specification of protein quantitative kit for abbkine BCA method
解析创客教育的知识迁移和分享精神
示波器探头对测量带宽的影响
Duchefa low melting point agarose PPC Chinese and English instructions
教你自己训练的pytorch模型转caffe(三)
随机推荐
解析创客教育的知识迁移和分享精神
Clear app data and get Icon
poj 3414 Pots (bfs+线索)
Talk about my fate with some programming languages
研学旅游实践教育的开展助力文旅产业发展
AITM 2-0003 水平燃烧试验
Abnova maxpab mouse derived polyclonal antibody solution
XML建模
学习机器人无从下手?带你体会当下机器人热门研究方向有哪些
当用户登录,经常会有实时的下拉框,例如,输入邮箱,将会@qq.com,@163.com,@sohu.com
ts 之 属性的修饰符public、private、protect
When a user logs in, there is often a real-time drop-down box. For example, entering an email will @qq com,@163. com,@sohu. com
php中explode函数存在的陷阱
Mode - "Richter replacement principle"
Learning notes of SAS programming and data mining business case 19
Écrire une interface basée sur flask
When steam education enters personalized information technology courses
Clion-MinGW编译后的exe文件添加ico图标
ViewRootImpl和WindowManagerService笔记
Determine the best implementation of horizontal and vertical screens