关键词：
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | | o | o | o +-------------> 0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出: 4 解释: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
看到此题，第一想法是用一个数据结构来表示某一条直线，直线的表达式有y = ax + b ,那提取出 a和b是不是就可以了，写完发现还有x = 1这种直线。然后想通过hashmap来保存直线对应的点数，如果参数a和b是个1/3这种值，由于精度问题，算出来的两个直线的数据结构的hash值就不一样，hashmap就是认为是两个key。 最后无奈换成分数表达式 y = (a1/a2)*x + b1/b2; b1/b2 = (a2*y - a1*x)/a2;这样4个int变量，就可以精确表示一条直线.当然，分数需要进行约分！
struct FPoint int a1; int a2; int b1; int b2; FPoint() : a1(0), a2(0), b1(0), b2(0) FPoint(int _a1, int _a2) if (_a1 * _a2 > 0) a1 = abs(_a1); a2 = abs(_a2); else a1 = -1 * abs(_a1); a2 = abs(_a2); b1 = 0; b2 = 1; bool Contain(Point p)const long long int t1 = 1L, t2 = 1L; t1 = t1 * p.y * (a2*b2); t2 = t2 * a1*b2*p.x + b1*a2; return a2 == 0 ? p.x == b1 / b2 : t1 == t2; void Normal() if (a1 == 0 && a2 == 0) else if (a1 == 0) a2 = 1; else if (a2 == 0) a1 = 1; else int s = a1*a2 > 0 ? 1 : -1; a1 = abs(a1); a2 = abs(a2); int _gcd = GCD(a1, a2); a1 = s * a1 / _gcd; a2 = a2 / _gcd; if (b1 == 0) b2 = 1; else s = b1*b2 > 0 ? 1 : -1; b1 = abs(b1); b2 = abs(b2); _gcd = GCD(b1, b2); b1 = s * b1 / _gcd; b2 = b2 / _gcd;
//最大公约数 int GCD(int a, int b) int m = a, n = b, r; if (m < n) int temp = m; m = n; n = temp; r = m % n; while (r) m = n; n = r; r = m % n; return n; ; struct RecordHash size_t operator()(const FPoint& f) const return hash<int>()(f.a1) ^ hash<int>()(f.a2) ^ hash<int>()(f.b1) ^ hash<int>()(f.b2); ; struct RecordCmp bool operator()(const FPoint& f1, const FPoint& f2) const return f1.a1 == f2.a1 && f1.a2 == f2.a2 &&f1.b1 == f2.b1&&f1.b2 == f2.b2; ; class Solution public: FPoint GetPoint(Point a, Point b) FPoint f(b.y - a.y, b.x - a.x ); if (f.a2 == 0) f.b1 = a.x; f.b2 = 1; else f.b1 = (f.a2*a.y - f.a1*a.x); f.b2 = f.a2; return f; int maxPoints(vector<Point>& points) if (points.size() <= 1) return points.size(); unordered_set<int> index_set; unordered_map<FPoint, int, RecordHash, RecordCmp> line_map; int max_point = 0; for (int i = 0; i < points.size(); i++) unordered_map<FPoint, int, RecordHash, RecordCmp>::iterator itr = line_map.begin(); for (; itr != line_map.end(); itr++) if (itr->first.Contain(points[i])) itr->second++; max_point = max(max_point, itr->second); if (index_set.count(i) == 0)index_set.insert(i); for (int r = 0; r < points.size() ; r++) if (r != i && index_set.count(r) == 0) FPoint f = GetPoint(points[i], points[r]); f.Normal(); if (line_map[f] == 0) line_map[f]++; if (index_set.count(i) == 0) index_set.insert(i); max_point = max(max_point, line_map[f]); return max_point; ;
直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。functionmaxPoints(points)if(points.length==1)return1letnumber=0for(leti=0;i<points.length-1;i++)letitem=points[i]for(letj=i+1;j<points.length;j++ 查看详情
题目地址(149.直线上最多的点数)(代码片段)
题目地址(149.直线上最多的点数)https://leetcode.cn/problems/max-points-on-a-line/题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1,1],[2,2],[... 查看详情
题目地址(149.直线上最多的点数)(代码片段)
题目地址(149.直线上最多的点数)https://leetcode.cn/problems/max-points-on-a-line/题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1,1],[2,2],[... 查看详情
leetcode0149.直线上最多的点数(代码片段)
【LetMeFly】149.直线上最多的点数力扣题目链接：https://leetcode.cn/problems/max-points-on-a-line/给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=... 查看详情
leetcode149.直线上最多的点数(代码片段)
...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<=300point 查看详情
leetcode第149题—直线上最多的点数—python实现(代码片段)
...odeNo.149categories:OJLeetCodetags:ProgramingLeetCodeOJLeetCode第149题—直线上最多的点数自己代码的开源仓库:clickhere欢迎Star和Fork😃题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一... 查看详情
leetcode第149题—直线上最多的点数—python实现(代码片段)
...odeNo.149categories:OJLeetCodetags:ProgramingLeetCodeOJLeetCode第149题—直线上最多的点数自己代码的开源仓库:clickhere欢迎Star和Fork😃题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一... 查看详情
leetcodeno.149直线上最多的点数(代码片段)
...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<=300points[i].l 查看详情
leetcodeno.149直线上最多的点数(代码片段)
一、题目描述给你一个数组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, 查看详情
直线上最多的点数(代码片段)
classSolutionpublicintmaxPoints(int[][]points)if(points.length==1)return1;Map<Double,Integer>map=newHashMap<>();intmax=Integer.MIN_VALUE;for(int[]point1:points)for(int[]point2:points)doublek=(double)(point2[1]-point1[1])/(double)(point2[0]-point1[0]);map.put(k,map.get... 查看详情
直线上最多的点数(代码片段)
classSolutionpublicintmaxPoints(int[][]points)if(points.length==1)return1;Map<Double,Integer>map=newHashMap<>();intmax=Integer.MIN_VALUE;for(int[]point1:points)for(int[]point2:points)doublek=(double)(point2[1]-point1[1])/(double)(point2[0]-point1[0]);map.put(k,map.get... 查看详情
数据结构与算法之深入解析“直线上最多的点数”的求解思路与算法示例(代码片段)
一、题目要求给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点，求最多有多少个点在同一条直线上。示例1：输入：points=[[1,1],[2,2] 查看详情
day4直线上最多的点数循环链表四数相加2(代码片段)
四数相加2对下一个题的方式有启发，使用dict存储后两个之和classSolution(object):deffourSumCount(self,A,B,C,D):Dict=foriinrange(len(C)):forjinrange(len(D)):ifC[i]+D[j]inDict:Dict[C[i]+D[j]]+=1else:Dict[ 查看详情
2021-09-03：直线上最多的点数。给你一个数组points，其中points[i]=[xi,yi]表示x-y平面上的一个点。求最多有多少个点在同一条直线上。力扣149。(代码片(代码片段)
2021-09-03：直线上最多的点数。给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。力扣149。福大大答案2021-09-03：具体见代码。代码用golang编写。代码如下：packagem... 查看详情
149.maxpointsonaline
Given n pointsona2Dplane,findthemaximumnumberofpointsthatlieonthesamestraightline. 求二维平面上n个点中，最多共线的点数。 1、比较直观的方法是，三层循环，以任意两点划线，判断第三个点是否在这条直线上。 ... 查看详情
149.maxpointsonaline
Given n pointsona2Dplane,findthemaximumnumberofpointsthatlieonthesamestraightline. 要求是输入n个坐标点，输出最多有多少个点在同一条直线上。 代码提交如下：1intSolution::maxPoints(vector<Point>&points)2{3if( 查看详情
直线交点数种类p2789直线交点数(代码片段)
题目平面上有N条直线，且无三线共点，那么这些直线能有多少不同的交点数？https://www.luogu.com.cn/problem/P2789题目分析我们将n条直线编号,分别称为直线1、直线2、…、直线n。直线2与直线1最多有一个交点，直线3与直线1和直线2... 查看详情