沈阳科技网站首页,it外包服务公司排名,网站开发证,营销型网站效果题目
给你一个数组 points #xff0c;其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 示例 1#xff1a; 输入#xff1a;points [[1,1],[2,2],[3,3]] 输出#xff1a;3
示例 2#xff1a; 输入#xff1a;points [[1,1],[3,…题目
给你一个数组 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 300points[i].length 2-104 xi, yi 104points 中的所有点 互不相同
解题思路
遍历每一个点标i以点标i为原点向后遍历后面的所有点标记作j计算i与j之间的斜率和截距因为统一以i为起点所以不需要计算截距只需要用斜率就能表示一条直线使用map记录斜率因为都经过点标i所以相同斜率即为同一条直线上的点考虑到斜率可能是小数的精度问题因此将斜率化成最简分数的形式使用辗转相除法求最大公约数再使用字符串进行表示。最后斜率相同的直线个数1因为一条直线是由两个点表示的因此n条直线里面含有n1个点就是处于同一直线下的点标数量。
辗转相除法
做法用较大数除以较小数再用出现的余数第一余数去除除数再用出现的余数第二余数去除第一余数如此反复直到最后余数是0为止。
代码
class Solution {int gcd(int a, int b) {return b 0 ? a : gcd(b, a % b);}public int maxPoints(int[][] points) {int npoints.length,res1;for (int i 0; i n; i) {HashMapString, Integer map new HashMap();int x1points[i][0],y1points[i][1];int max0;for (int j i1; j n; j) {int x2points[j][0],y2points[j][1];int ax1-x2,by1-y2;int gcd gcd(a, b);String key (a / gcd) (b / gcd);map.put(key,map.getOrDefault(key,0)1);maxMath.max(max,map.get(key));}resMath.max(res,max1);}return res;}
}
