My java code , using gcd of a rational number


  • 2
    T

    the code structure is simple. this problem is really all about how to implement hashCode() and equals(). here I represent the denominator and nominator of a rational deltay/deltax

        /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        
        static class Line {
            int deltax;
            int deltay;
            
            int cross1;
            int cross2;
            
            public Line(int deltax, int deltay, int x0, int y0) {
                // shrink 
                if (deltax == 0) {deltay = 1; cross1 = x0; cross2=0; }
                else if (deltay == 0) { deltax = 1; cross1 = y0; cross2 = 0;}
                else {
                    int gcd = gcd(deltax, deltay);
                    deltax = deltax/gcd;
                    deltay = deltay/gcd;
                    if (deltax <0) {
                        deltax = - deltax;
                        deltay = - deltay;
                    }
                    this.deltax = deltax;
                    this.deltay = deltay;
                    
                    cross1 = y0 * deltax - x0 * deltay;
                    cross2 = deltax * deltay;
                    if (cross1 ==0) cross2 = 1;
                    else {
                    gcd = gcd(cross1, cross2);
                    cross1 /= gcd;
                    cross2 /= gcd;
                    }
                }
            }
            
            public int hashCode() {
                return deltax*deltay + cross1 + cross2 + deltax;
            }
            public boolean equals(Object obj) {
                if (obj == null) return false;
                if (! (obj instanceof Line )) return false;
                Line obj2 = (Line) obj;
                return obj2.deltax == deltax && obj2.deltay == deltay && obj2.cross1 == cross1 && obj2.cross2 == cross2;
            }
            
      static int gcd(int a, int b)
    {
      while(a!=0 && b!=0) // until either one of them is 0
      {
         int c = b;
         b = a%b;
         a = c;
      }
      return a+b; // either one is 0, so return the non-zero value
    }
        }
        
        public int maxPoints(Point[] points) {
            Map<Line, Set<Integer>> map = new HashMap<Line, Set< Integer>>();
            if (points.length == 1 ) { return 1;}
            for(int i=0;i<points.length-1;i++) {
                for(int j=i+1;j<points.length;j++) {
                    Line l = new Line(points[i].x - points[j].x, points[i].y - points[j].y, points[i].x, points[i].y );
                    if( map.containsKey(l) ) {
                        map.get(l).add(i);
                        map.get(l).add(j);
                    } else {
                        map.put(l,new HashSet<Integer>() );
                        map.get(l).add(i);
                        map.get(l).add(j);
                    }
                }
            }
            
            int best = 0;
            for(Map.Entry e: map.entrySet()) {
                Set cnt = (Set)e.getValue();
                best = Math.max(cnt.size(),best);
            }
            return best;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.