Leetcode 149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.Example 1:
Input: [,,]
Output: 3
Explanation:
^
|
| o
| o
|o
+------------->
01234
Example 2:
Input: [,,,,,]
Output: 4
Explanation:
^
|
|o
| o o
| o
|o o
+------------------->
0123456
class Solution:
def maxPoints(self, points: List]) -> int:
n = len(points)
res = 0
for i in range(n):
hashmap = collections.defaultdict(int)
local_max = 0
same_point = 1
n1 = points
for j in range(i + 1, n):
n2 = points
if n1 == n2 and n1 == n2:
same_point += 1
else:
slope = self.get_slope(n1, n2)
hashmap = hashmap + 1
local_max = max(local_max, hashmap)
res = max(res, local_max + same_point)
return res
def get_slope(self, n1: List, n2: List) -> List:
dx = n2 - n1
dy = n2 - n1
if dy == 0:
return (n1, 0)
if dx == 0:
return (0, n1)
d = self.gcd(dx, dy)
return (dy / d, dx / d)
def gcd(self, a, b):
if(b==0):
return a
else:
return self.gcd(b,a%b)
页:
[1]