科技进步法,铜陵网站优化,上海建设公司,学做网站视频教程LeetCode 149. 直线上最多的点数 给你一个数组 points #xff0c;其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 示例 1#xff1a; 输入#xff1a;points [[1,1],[2,2],[3,3]] 输出#xff1a;3 示例 2#xff1a; 输入其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 示例 1 输入points [[1,1],[2,2],[3,3]] 输出3 示例 2 输入points [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出4 提示 1 points.length 300 points[i].length 2 -104 xi, yi 104 points 中的所有点 互不相同 恰巧AC但题解不对还是看大佬的解法吧
class Solution:def maxPoints(self, points: List[List[int]]) - int:if len(points) 1:return 1combine_mapping {}for i in range(2, len(points) 1):combine_mapping[math.comb(i, 2)] imapping defaultdict(lambda: 0)mapping[(0,0,0)] 1for i in range(len(points)):for j in range(i 1, len(points)):(x1, y1), (x2, y2) points[i], points[j]a, b, c y2 - y1, x1 - x2, x2 * y1 - x1 * y2d a if a else ba, b, c a / d, b / d, c / dmapping[(a, b, c)] 1res (0,0,0)for i in mapping:if combine_mapping[mapping[res]] combine_mapping[mapping[i]]:res ireturn combine_mapping[mapping[res]]
