力扣
本题的方法就是查找，但是测试用例中会有很多坑[[0,0],[94911150,94911151],[94911151,94911152]]；这两个不是一个点，但由于浮点数的精度问题，导致一直计算为1个斜率。
处理方法：dy X 1000 / dx X 1000或者利用最简分数：9/18=3/6=1/2
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
链接：https://leetcode-cn.com/problems/max-points-on-a-line
题解：
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
#两点共线
if len(points) < 3:
return len(points)
from collections import defaultdict
res = 0
for i in range(len(points)):
record = defaultdict(int)
samepoint = 0
#依次遍历所有的两两点，注意这里面有重复的点，所以需要samepoint++
for j in range(i + 1, len(points)):
# if i != j:
if points[i] == points[j]:
samepoint += 1
else:
record[get_slope(points, i, j)] += 1
for v in record.values():
# 这里加上重复的点，找最多共线的
res = max(v + samepoint, res)
# print(v)
# 这里是为了避免点都一样，返回samepoint
res = max(res, samepoint)
return res + 1
# 方法一：利用斜率，精度不够乘以1000来凑，必须分别乘，直接乘1000000还是会出现问题
# def get_slope(self, points, i, j):
# if points[j][1] - points[i][1] == 0:
# return 'inf'
# else:
# return (points[j][0]-points[i][0])*1000 / (points[j][1]-points[i][1])*1000
# 方法二：求最大公约数，这里不能用内嵌的函数，不懂为什么
# 求最大公约数
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
def get_slope(points, i, j):
if points[j][1] - points[i][1] == 0:
return 'inf'
else:
g = gcd(points[j][0] - points[i][0], points[j][1] - points[i][1])
# if g != 0:
numerator = (points[j][0] - points[i][0]) // g
denominator = (points[j][1] - points[i][1]) // g
return '{}/{}'.format(numerator, denominator)
方法二：41 / 41 个通过测试用例
状态：通过 执行用时: 112 ms 内存消耗: 13.8 MB
方法一：41 / 41 个通过测试用例
状态：通过 执行用时: 76 ms 内存消耗: 13.6 MB
