149. Max Points on a Line

系统管理员 2021-12-22 06:55 200阅读 0赞

class Solution {
        public int maxPoints(Point[] points) {
            if(points.length<3)
                return points.length;
            int res=0;
            Map<Integer, Map<Integer,Integer>> map=new HashMap<Integer, Map<Integer, Integer>>();
            for(int i=0;i<points.length;i++)
            {
                map.clear();
                int samepoint=1,max=0;
                for(int j=i+1;j<points.length;j++)
                {
                    int x=points[i].x-points[j].x;
                    int y=points[i].y-points[j].y;
                    if(x==0&&y==0)
                        samepoint++;
                    else
                    {
                        int d=gcd(x,y);
                        x/=d;
                        y/=d;
            			if (map.containsKey(x)){
            				if (map.get(x).containsKey(y)){
            					map.get(x).put(y, map.get(x).get(y)+1);
            				}else{
            					map.get(x).put(y, 1);
            				}   					
            			}else{
            				Map<Integer,Integer> m = new HashMap<Integer,Integer>();
            				m.put(y, 1);
            				map.put(x, m);
            			}
            			max=Math.max(max, map.get(x).get(y));                    
                    }
                    res=Math.max(max+samepoint,res);
                }
            }
            return res;
        }
        private int gcd(int a, int b){
            if(b==0)
                return a;
            return gcd(b, a%b);
        }
    }

转载于:https://www.cnblogs.com/asuran/p/7679790.html

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 149. Max Points on a Line |149. 直线上最多的点数（Java）

题目 [https://leetcode.com/problems/max-points-on-a-line/][https_leetcode.com_problems_

今天药忘吃喽~/ 2022年09月01日 15:43/ 0 赞/ 150 阅读

相关 Max Points on a Line--LeetCode

Given n points on a 2D plane, find the maximum number of points that lie on the same str

旧城等待，/ 2022年08月07日 13:35/ 0 赞/ 160 阅读

相关【leetcode每日一题】149.Max Points on a line

题目：Given n points on a 2D plane, find the maximum number of points that lie on the same

清疚/ 2022年08月04日 12:56/ 0 赞/ 126 阅读

相关 lintcode Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same str

本是古典何须时尚/ 2022年07月15日 13:19/ 0 赞/ 142 阅读

相关 LeetCode149—Max Points on a Line

原题 [原题链接][Link 1] > Given n points on a 2D plane, find the maximum number of points

￡神魔★判官ぃ/ 2022年07月15日 09:21/ 0 赞/ 134 阅读

相关 leetcode 149. Max Points on a Line 计算斜率的问题 + 直接暴力求解即可

Given n points on a 2D plane, find the maximum number of points that lie on the same str

﹏ヽ暗。殇╰゛Y/ 2022年06月08日 06:24/ 0 赞/ 153 阅读

相关 3.max-points-on-a-line 直线上的最多点

题目描述 Given n points on a 2D plane, find the maximum number of points that lie on the

我不是女神ヾ/ 2022年06月06日 07:20/ 0 赞/ 207 阅读

相关 LeetCode刷题笔记（穷举）：max-points-on-a-line

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

向右看齐/ 2022年05月31日 01:35/ 0 赞/ 171 阅读

相关 [Leetcode] Max Points on a Line 直线上最多的点数

Max Points on a Line > Given n points on a 2D plane, find the maximum number of point

港控/mmm°/ 2022年02月17日 02:43/ 0 赞/ 194 阅读

相关 149. Max Points on a Line

class Solution { public int maxPoints(Point[] points) { if(point

系统管理员/ 2021年12月22日 06:55/ 0 赞/ 201 阅读