首页 > itarticle > leetcode “149. max points on a line”

leetcode “149. max points on a line”

admin 11月 13, 2020 0

LeetCode link

Intuition

  • Each two points can lie on one line, use a map to save all the lines, key is the line(no matter the form you save, here is using the string(a_b) to identify the line), value is all the index of the points.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class Solution {
    public int maxPoints(Point[] points) {
        if (points.length == 1) {
            return 1;
        }
        Map<String, Set<Integer>> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                Point p1 = points[i];
                Point p2 = points[j];
                double a = (p1.y - p2.y) * 1.0 / (p1.x - p2.x);
                double b = (p1.x * p2.y - p2.x * p1.y) * 1.0 / (p1.x - p2.x);
                String key = a + "_" + b;
                map.putIfAbsent(key, new HashSet<Integer>());
                Set set = map.get(key);
                set.add(i);
                set.add(j);
                max = Math.max(max, set.size());
            }
        }
        return max;
    }
}

problem

WA.

reason

The points may be duplicate.

modification

  • When two points are the same, continue.
  • When meet a new point on a line, add the count of the point to the point-number of the line at once. Mark this point is added of this line.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
class Solution {
    public int maxPoints(Point[] points) {
        if (points.length == 1) {
            return 1;
        }
        Map<String, Set<Integer>> map = new HashMap<>();
        Map<String, Integer> counts = new HashMap<>();
        Map<String, Integer> maxCounts = new HashMap<>();
        for (Point p: points) {
            String key = p.x + "_" + p.y;
            counts.putIfAbsent(key, 0);
            counts.put(key, counts.get(key) + 1);
        }
        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                Point p1 = points[i];
                Point p2 = points[j];
                String key = "";
                if (p1.x == p2.x && p1.y == p2.y) {
                    continue;
                }
                if (p1.x == p2.x) {
                    key = p1.x + "_";
                } else if (p1.y == p2.y) {
                    key = "_" + p1.y;
                } else {
                    double a = (p1.y - p2.y) * 1.0 / (p1.x - p2.x);
                    double b = (p1.x * p2.y - p2.x * p1.y) * 1.0 / (p1.x - p2.x);
                    if (b == 0) {
                        b = 0;
                    }
                    key = a + "_" + b;
                }
                map.putIfAbsent(key, new HashSet<Integer>());
                maxCounts.putIfAbsent(key, 0);
                Set set = map.get(key);
                int maxCount = maxCounts.get(key);
                if (!set.contains(p1.x + "_" + p1.y)) {
                    maxCount += counts.get(p1.x + "_" + p1.y);
                }
                if (!set.contains(p2.x + "_" + p2.y)) {
                    maxCount += counts.get(p2.x + "_" + p2.y);
                }
                set.add(p1.x + "_" + p1.y);
                set.add(p2.x + "_" + p2.y);
                max = Math.max(max, maxCount);
                maxCounts.put(key, maxCount);
            }
        }
        return max;
    }
}

problem

WA.

reason

Miss the situation that all the points are the same.

modification

add the case of all points are the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Map<String, Set<Integer>> map = new HashMap<>();
Map<String, Integer> counts = new HashMap<>();
Map<String, Integer> maxCounts = new HashMap<>();
int pointCounts = 0;
for (Point p: points) {
    String key = p.x + "_" + p.y;
    if (counts.putIfAbsent(key, 0) == null) {
        pointCounts++;
    }
    counts.put(key, counts.get(key) + 1);
}
if (pointCounts <= 1) {
    return points.length;
}

problem

WA.

Input:
[[0,0],[94911151,94911150],[94911152,94911151]]
Output:
3
Expected:
2

reason

Big number, the precision is not enough.

modification

Here’s the answer found on the net.I’m still confused by the solution.

  • To get rid of the precision problems, we treat slope as pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by their gcd before inserting into map. In below code points which are vertical or repeated are treated separately.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
public class Solution{
    public int maxPoints(Point[] points) {
    	if (points==null) return 0;
    	if (points.length<=2) return points.length;
    	Map<Integer,Map<Integer,Integer>> map = new HashMap<Integer,Map<Integer,Integer>>();
    	int result=0;
    	for (int i=0;i<points.length;i++){
    		map.clear();
    		int overlap=0,max=0;
    		for (int j=i+1;j<points.length;j++){
    			int x=points[j].x-points[i].x;
    			int y=points[j].y-points[i].y;
    			if (x==0&&y==0){
    				overlap++;
    				continue;
    			}
    			int gcd=generateGCD(x,y);
    			if (gcd!=0){
    				x/=gcd;
    				y/=gcd;
    			}
    			if (map.containsKey(x)){
    				if (map.get(x).containsKey(y)){
    					map.get(x).put(y, map.get(x).get(y)+1);
    				}else{
    					map.get(x).put(y, 1);
    				}   					
    			}else{
    				Map<Integer,Integer> m = new HashMap<Integer,Integer>();
    				m.put(y, 1);
    				map.put(x, m);
    			}
    			max=Math.max(max, map.get(x).get(y));
    		}
    		result=Math.max(result, max+overlap+1);
    	}
    	return result;
    }
    private int generateGCD(int a,int b){
    	if (b==0) return a;
    	else return generateGCD(b,a%b);
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能