正文

149maxpointsonaline直线上最多的点数

lina2014  lina2014  2022-10-31  765

关键词：

给定二维平面上有 n 个点，求最多有多少点在同一条直线上。

详见：https://leetcode.com/problems/max-points-on-a-line/description/

Java实现：

/**
 * Definition for a point.
 * class Point 
 *     int x;
 *     int y;
 *     Point()  x = 0; y = 0; 
 *     Point(int a, int b)  x = a; y = b; 
 * 
 */
class Solution 
    public int maxPoints(Point[] points) 
        if (points == null || points.length == 0)
            return 0;
        
        Map<String, List<Point>> slopes = new HashMap<>();
        int res = 0;
        for (int i = 0; i < points.length; i++)
            //starting from different points, could be same slope but they are not in a line
            slopes = new HashMap<String, List<Point>>();
            int samePoints = 1;
            int max = 0;
            for (int j = i + 1; j < points.length; j++)
                int deltaY = points[j].y - points[i].y;
                int deltaX = points[j].x - points[i].x;
                if (deltaY == 0 && deltaX == 0)
                    samePoints++;
                    continue;
                
                int gcd = getGCD(deltaX, deltaY);
                deltaY /= gcd;
                deltaX /= gcd;
                String slope = deltaY + ":" + deltaX;
                if (!slopes.containsKey(slope))
                    slopes.put(slope, new ArrayList<Point>());
                
                slopes.get(slope).add(points[j]);
                max = Math.max(max, slopes.get(slope).size());
            
            res = Math.max(res, max + samePoints);
        
        return res;
    

    private int getGCD(int a, int b)
        if (b == 0)
            return a;
         else 
            return getGCD(b, a % b);

参考：https://www.jianshu.com/p/0073d059687d

题目地址(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.直线上最多的点数)(代码片段)

leetcode第149题—直线上最多的点数—python实现(代码片段)

...odeNo.149categories:OJLeetCodetags:ProgramingLeetCodeOJLeetCode第149题—直线上最多的点数自己代码的开源仓库:clickhere欢迎Star和Fork😃题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一... 查看详情

leetcode第149题—直线上最多的点数—python实现(代码片段)

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 查看详情

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, 查看详情

leetcode0149.直线上最多的点数(代码片段)

【LetMeFly】149.直线上最多的点数力扣题目链接：https://leetcode.cn/problems/max-points-on-a-line/给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。示例1：输入：points=... 查看详情

149.maxpointsonaline

Given n pointsona2Dplane,findthemaximumnumberofpointsthatlieonthesamestraightline. 要求是输入n个坐标点，输出最多有多少个点在同一条直线上。代码提交如下：1intSolution::maxPoints(vector<Point>&points)2{3if( 查看详情

149.maxpointsonaline

Given n pointsona2Dplane,findthemaximumnumberofpointsthatlieonthesamestraightline. 求二维平面上n个点中，最多共线的点数。 1、比较直观的方法是，三层循环，以任意两点划线，判断第三个点是否在这条直线上。 ... 查看详情

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... 查看详情

直线上最多的点数

给定一个二维平面，平面上有 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++ 查看详情

直线上最多的点数(代码片段)

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[ 查看详情

149.maxpointsonaline

classSolution{publicintmaxPoints(Point[]points){if(points.length<3)returnpoints.length;intres=0;Map<Integer,Map<Integer,Integer>>map=newHashMap<Integer,Map<Integer,Integer>> 查看详情

149.maxpointsonaline

题目：Given n pointsona2Dplane,findthemaximumnumberofpointsthatlieonthesamestraightline. 思路：这道题看起来并不难，但是有很多需要注意的点，我用了很久的时间才通过这道题。大致的思路是这样的，使用穷举法，对于任意点P，计算... 查看详情