2 Java Solutions, similar algorithm, different implementation


  • 0
    M

    Solution 1:

            public int maxPoints(Point[] points) {
    		int max = 0;
    		if (points == null || points.length == 0) return 0;
    		int n = points.length;
    		if (n == 1) return 1;
    		for (int i = 0; i < n - 1; ++i) {
    			Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    			int dup = 0, lclmax = 0;
    			for (int j = i + 1; j < n; ++j) {
    				int x = points[j].x - points[i].x;
    				int y = points[j].y - points[i].y;
    				if (x == 0 && y == 0) {
    					++dup;
    					continue;
    				}
    				int gcd = gcd(x, y);
    				x /= gcd;
    				y /= gcd;
    				if (!map.containsKey(x)) map.put(x, new HashMap<Integer, Integer>());
    				if (!map.get(x).containsKey(y)) map.get(x).put(y, 0);
    				map.get(x).put(y, map.get(x).get(y) + 1);
    				lclmax = Math.max(lclmax, map.get(x).get(y));
    			}
    			max = Math.max(max, dup + lclmax + 1);
    		}
    		return max;
    	}
    	
    	private int gcd(int a, int b) {
    		if (b == 0) return a;
    		return gcd(b, a % b);
    	}
    

    Solution 2:

            private class Frac {
    		int dvd, dvs;
    		public Frac (int a, int b) {
    			int gcd = gcd(a, b);
    			dvd = a / gcd;
    			dvs = b / gcd;
    		}
    		private int gcd(int a, int b) {
    			if (b == 0) return a;
    			return gcd(b, a % b);
    		}
    		@Override
    		public int hashCode() {
    			return dvd * 100007 + dvs * 1007 + 17;
    		}
    		@Override
    		public boolean equals(Object o) {
    			if (!(o instanceof Frac)) return false;
    			Frac other = (Frac) o;
    			return dvd == other.dvd && dvs == other.dvs;
    		}
    	}
    	private class Line{
    		Frac a, b;
    		public Line(Point p1, Point p2) {
    			if (p1.x == p2.x) {
    				a = null;
    				b = new Frac(p1.x, 1);
    			} else {
    				a = new Frac(p1.y - p2.y, p1.x - p2.x);
    				b = new Frac(p1.x * p2.y - p2.x * p1.y, p1.x - p2.x);
    			}		
    		}
    		@Override
    		public int hashCode() {
    			return (a == null ? 0 : a.hashCode() * 100013) + b.hashCode() * 10013 + 13;
    		}
    		@Override
    		public boolean equals(Object o) {
    			if (!(o instanceof Line)) return false;
    			Line other  = (Line) o;
    			return (a == null && other.a == null || a.equals(other.a)) && b.equals(other.b);
    		}
    	}
    	public int maxPoints(Point[] points) {
            if (points == null || points.length == 0) return 0;
    		int n = points.length;
    		if (n == 1) return 1;
    		Map<Line, Set<Point>> map = new HashMap<>();
    		int max = 0;
    		for (int i = 0; i < n - 1; ++i) {
    			for (int j = i + 1; j < n; ++j) {
    				Line line = new Line(points[i], points[j]);
    				if (!map.containsKey(line)) {
    					map.put(line, new HashSet<Point>());
    				}
    				map.get(line).add(points[i]);
    				map.get(line).add(points[j]);
    				max = Math.max(max, map.get(line).size());
    			}
    		}
    		return max;
        }
    

Log in to reply
 

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