首页 > 代码库 > Leetcode-Max Points on a Line
Leetcode-Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:
1 /** 2 * Definition for a point. 3 * class Point { 4 * int x; 5 * int y; 6 * Point() { x = 0; y = 0; } 7 * Point(int a, int b) { x = a; y = b; } 8 * } 9 */ 10 11 class Line { 12 int slopeX; 13 int slopeY; 14 int b; 15 boolean negSlope; 16 boolean samePointLine; 17 Set<Point> pointSet; 18 String uid; 19 public Line(int sx, int sy, int bb,boolean spl){ 20 if (sx<0) slopeX = -sx; 21 else slopeX = sx; 22 23 if (sy<0) slopeY = -sy; 24 else slopeY = sy; 25 26 if (sy==0) slopeX=1; 27 if (sx==0) slopeY=1; 28 b = bb; 29 30 if (sx<0 || sy<0) negSlope = true; 31 else negSlope = false; 32 33 samePointLine = spl; 34 35 pointSet = new HashSet<Point>(); 36 37 uid = Integer.toString(slopeX)+"/"+Integer.toString(slopeY)+"/"+Double.toString(b)+"/"+Boolean.toString(negSlope)+"/"+Boolean.toString(samePointLine); 38 } 39 40 public boolean equals(Line l2){ 41 if (uid==l2.uid) 42 return true; 43 else return false; 44 } 45 46 } 47 48 49 public class Solution { 50 public int maxPoints(Point[] points) { 51 if (points.length==1) return 1; 52 53 Set<Point> pSet = new HashSet<Point>(); 54 for (int i=0;i<points.length;i++) pSet.add(points[i]); 55 56 Map<String,Line> lineList = new HashMap<String,Line>(); 57 List<String> uidList = new ArrayList<String>(); 58 for (int i=1;i<points.length;i++){ 59 Set<Point> curPSet = new HashSet<Point>(); 60 curPSet.addAll(pSet); 61 for (int j=0;j<i;j++) 62 if (curPSet.contains(points[j])){ 63 //This point has not been checked. 64 //Calculate the line formed by i and j 65 int ix = points[i].x; 66 int iy = points[i].y; 67 int jx = points[j].x; 68 int jy = points[j].y; 69 int sx = points[i].x-points[j].x; 70 int sy = points[i].y-points[j].y; 71 Line l1 = null; 72 //infnite slope line. 73 if (sx==0 && sy==0) 74 l1 = new Line(points[i].x,points[i].y,0,true); 75 else if (sx==0) 76 l1 = new Line(0,1,points[i].x,false); 77 else if (sy==0) 78 l1 = new Line(1,0,points[i].y,false); 79 else { 80 int bb = jy*ix-jx*iy; 81 int gcd = getGCD(sx,sy); 82 int gcd2 = getGCD(bb,sx); 83 sx = sx/gcd; 84 sy = sy/gcd; 85 bb = bb/gcd2; 86 l1 = new Line(sx,sy,bb,false); 87 } 88 89 //Check each exsiting line. 90 if (lineList.containsKey(l1.uid)){ 91 lineList.get(l1.uid).pointSet.add(points[i]); 92 lineList.get(l1.uid).pointSet.add(points[j]); 93 curPSet.removeAll(lineList.get(l1.uid).pointSet); 94 95 } else { 96 lineList.put(l1.uid,l1); 97 uidList.add(l1.uid); 98 l1.pointSet.add(points[i]); 99 l1.pointSet.add(points[j]);100 }101 }102 }103 104 int max = 0;105 for (int i=0;i<uidList.size();i++)106 if (lineList.get(uidList.get(i)).pointSet.size()>max)107 max = lineList.get(uidList.get(i)).pointSet.size();108 109 return max;110 111 }112 113 114 public int getGCD(int a, int b){115 int left = a%b;116 while (left!=0){117 a=b;118 b=left;119 left=a%b;120 }121 return b;122 }123 124 125 }
Leetcode-Max Points on a Line
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。