149. Max Points on a Line
平面上有很多点，问你最多能让几点共线
Example 1:
https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
思路:
1.对每个点都去算其他点和他的斜率 一样的话就是在同一条线上
斜率可以拿来当成 dict 的 key 最后检查哪个 key 的 value 最高就好
自己和自己的斜率最后再扣掉
朴实的O(n^2)
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
res = 0
for p1 in points:
slope = defaultdict(int)
for p2 in points:
if p1[0] - p2[0] != 0:
slope[(p1[1] - p2[1]) / (p1[0] - p2[0])] += 1
else:
slope[inf] += 1
slope[inf] -= 1
res = max(res, max(slope.values()))
return res+1