AUG!!! 28ms JAVA Solution! Use your Object Oriented thoughts! O(n2) Commented.


  • 0
    public class Solution {
        class Line{
            double epsilon = 0.0001;//difference within this range is considered to be the same. You could delete it or change this number to any one as long as it can work. 
            double yIntercept;//Basic idea that you must agree is that a slope and y-intercept can determine a line
            double slope;
            boolean infiniteSlope = false;//for lines which are perpendicular to x-axis, this is true;
            Line(Point p1, Point p2){
                if(p1.x == p2.x){
                    this.yIntercept = p1.x;
                    infiniteSlope = true;
                }else{
    //Compute the slope and y-intercept when the line is not perpendicular to x-axis
                    slope = (double)(p1.y - p2.y)/(p1.x - p2.x);
                    yIntercept = (double)p1.y - slope*p1.x;
                }
            }
    // The following is the key for this code. 
    // We need to overwrite hashCode() and equals() function here. We are going to save Line as the key and points on the Line as values into hashmap.
    //When we are searching whether a Line exists in the hashMap, containsKey method will call hashCode() function to find if the hashCode of the key we are searching matches any  
    // keys' hashCode in the map.If there is a match, then it will continue to call equals method to judge whether they are really equal. If yes, return true, if not, return false;
    
    //Overwrite hashCode function 
            public int hashCode(){
    // Here, you can use any calculation to return values which can distinguish different line, and return the same value when two line are the same.
                long yTemp =  (long)(yIntercept * 10000);//I chose 10000, because I chose .0001 as tolerance
                long slopeTemp = (long) (this.infiniteSlope?0:this.slope*10000);
                return (int)(yTemp/123+slopeTemp/313);//123 and 313 can be replaced
            }
    // One thing you really need to pay attention here is that parameter here must be Object, and then you can change it into Line.
            public boolean equals(Object obj){
                Line l = (Line) obj;
                if(this.infiniteSlope){
                    return l.infiniteSlope ? (Math.abs(this.yIntercept - l.yIntercept) < epsilon):false;
                }
                if(!l.infiniteSlope){
                    return Math.abs(this.yIntercept - l.yIntercept) < epsilon && Math.abs(this.slope - l.slope) < epsilon;
                }
                return false;
            }
            /*public void print(){
                System.out.println((infiniteSlope?"This one has a infiniteSlope":("The slope is " + this.slope)) + " the yIntercept is "+ yIntercept+" and hasCode is " +this.hashCode());
            }*/
            
        }
        public int maxPoints(Point[] points) {
            if(points == null || points.length == 0)
                return 0;
            if(points.length < 3)
                return points.length;
            int maxPointsOnLine = 2;
            Line currentLine; 
            HashSet pointsSet;
            HashMap<Line, HashSet<Point>> map = new HashMap<>();
    //Do not use arraylist here because you do not want to include duplicate points for the same line. 
            for(int i = 0; i < points.length; i++){
                for(int j = i+1; j < points.length; j++){
                    currentLine = new Line(points[i], points[j]);
                    if(!map.containsKey(currentLine)){
                        HashSet<Point> currentSet = new HashSet<>();
                        currentSet.add(points[i]);
                        currentSet.add(points[j]);
                        map.put(currentLine,currentSet);
                    }else{
                        pointsSet = map.get(currentLine);
                        pointsSet.add(points[i]);
                        pointsSet.add(points[j]);
                        map.put(currentLine,pointsSet);
                        if(maxPointsOnLine < pointsSet.size())
                            maxPointsOnLine = pointsSet.size();
                    }
                }
            }
            return maxPointsOnLine;
        }
    }
    

Log in to reply
 

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