149. Max Points on a Line 直线上最多的点数

@TOC

# 题目描述

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

``````Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o
+------------->
0  1  2  3  4
``````

Example 2:

``````Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6
``````

# 解题方法

# 字典+最大公约数

``````# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution(object):
def maxPoints(self, points):
"""
:type points: List[Point]
:rtype: int
"""
N = len(points)
res = 0
for i in range(N):
lines = collections.defaultdict(int)
duplicates = 1
for j in range(i + 1, N):
if points[i].x == points[j].x and points[i].y == points[j].y:
duplicates += 1
continue
dx = points[i].x - points[j].x
dy = points[i].y - points[j].y
delta = self.gcd(dx, dy)
lines[(dx / delta, dy / delta)] += 1
res = max(res, (max(lines.values()) if lines else 0) + duplicates)
return res

def gcd(self, x, y):
return x if y == 0 else self.gcd(y, x % y)
``````

# 日期

2018 年 11 月 10 日 —— 这么快就到双十一了？？