Java easy to understand w/ user defined Slope class w/ comments


  • 0

    idea is same as https://leetcode.com/discuss/9929/a-java-solution-with-notes
    But I improved it by using a user defined class Slope and it serves as a key for the hashtable.
    This simplified the code by reducing two maps into one.

    public class Solution {
        public int maxPoints(Point[] points) {
            if (points == null) {
                return 0;
            }
            int n = points.length;
            if (n < 3) {
                return n;
            }
            
            int res = 0;
            int dup = 0;//duplicate points
            int max;
            Map<Slope, Integer> slopes = new HashMap<>();
            for (int i = 0; i <= n - 2; i++) {
                slopes = new HashMap<>();
                dup = 0;
                for (int j = i + 1; j <= n - 1; j++) {
                    if (points[j].x == points[i].x && points[j].y == points[i].y) {
                        dup++;
                        continue;
                    }
                    Slope slope = new Slope(points[i], points[j]);
                    if (!slopes.containsKey(slope)) {
                        slopes.put(slope, 1);
                    } else {
                        slopes.put(slope, slopes.get(slope) + 1);
                    }
                }
                max = 0; // max points through points[i]
                for (Slope slope : slopes.keySet()) {
                   max = Math.max(max, slopes.get(slope));
                }
                max += dup + 1;
                res = Math.max(res, max);
            }
            return res;
        }
        
    }
    
    class Slope {
        int dx;
        int dy;
        Slope(Point a, Point b) {
            dx = a.x - b.x;
            dy = a.y - b.y;
            int gcd = gcd(dx, dy);
            dx /= gcd;
            dy /= gcd;
        }
        
        //override
        public boolean equals(Object s) {
            Slope slope = (Slope) s;
            return dx == slope.dx && dy == slope.dy;
        }
        //override hashCode to make sure equal Slope has equal hashCode
        public int hashCode() {
            return 31 * dx + dy;
        }
        
        private int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    }

Log in to reply
 

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