python实现leetcode之149. 直线上最多的点数

解题思路

任意两个不同的点：
根据他的斜率，与x轴的交点，与y轴的交点，确定一条直线，然后将这两点添加进去

149. 直线上最多的点数

代码

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 1: return len(points)

        mp = {}
        for i in range(len(points)):
            for j in range(i):
                if points[i] == points[j]: continue
                x1, y1 = points[i]
                x2, y2 = points[j]
                # key: (斜率, x轴交点, y轴交点)
                # key: (k, None, y轴交点)     斜率 k存在「y1 != y2」
                # key: (None, x轴交点, None)  斜率 k无穷大「y1 = y2」
                if x1 == x2:
                    key = (None, x1, None)
                else:
                    k = (y2-y1) / (x2-x1)
                    # y = k*x + b, b为y轴交点
                    b = y1 - k*x1
                    key = (k, None, b)
                if key not in mp: mp[key] = set()
                mp[key].add(tuple(points[i]))
                mp[key].add(tuple(points[j]))
        return max(len(v) for v in mp.values())