Leetcode 149. Max Points on a Line

Seawolf

1. Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: [[1,1],[2,2],[3,3]]
   
6. Output: 3
   
7. Explanation:
   
8. ^
   
9. |
   
10. |        o
    
11. |     o
    
12. |  o  
    
13. +------------->
    
14. 0  1  2  3  4
    
15. Example 2:
    
16. 
    
17. Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    
18. Output: 4
    
19. Explanation:
    
20. ^
    
21. |
    
22. |  o
    
23. |     o        o
    
24. |        o
    
25. |  o        o
    
26. +------------------->
    
27. 0  1  2  3  4  5  6

复制代码

1. class Solution:
   
2.     def maxPoints(self, points: List[List[int]]) -> int:
   
3.         n = len(points)
   
4.         res = 0
   
5.         
   
6.         for i in range(n):
   
7.             hashmap = collections.defaultdict(int)
   
8.             local_max = 0
   
9.             same_point = 1
   
10.             n1 = points[i]
    
11.             
    
12.             for j in range(i + 1, n):
    
13.                 n2 = points[j]
    
14.                 if n1[0] == n2[0] and n1[1] == n2[1]:
    
15.                     same_point += 1
    
16.                 else:
    
17.                     slope = self.get_slope(n1, n2)
    
18.                     hashmap[slope] = hashmap[slope] + 1
    
19.                     local_max = max(local_max, hashmap[slope])
    
20.                     
    
21.             res = max(res, local_max + same_point)
    
22.         
    
23.         return res
    
24.         
    
25.     def get_slope(self, n1: List[int], n2: List[int]) -> List[int]:
    
26.         dx = n2[0] - n1[0]
    
27.         dy = n2[1] - n1[1]
    
28. 
    
29.         if dy == 0:
    
30.             return (n1[1], 0)
    
31.         if dx == 0:
    
32.             return (0, n1[0])
    
33. 
    
34.         d = self.gcd(dx, dy)
    
35. 
    
36.         return (dy / d, dx / d)
    
37.    
    
38.     def gcd(self, a, b):
    
39.         if(b==0):
    
40.             return a
    
41.         else:
    
42.             return self.gcd(b,a%b)

复制代码