题目:
给你一个数组
points
,其中points[i] = [xi, yi]
表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
示例:
示例 1:
输入:points = [[1,1],[2,2],[3,3]]输出:[0,1]
解释:3
示例 2:输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4
解法:
遍历每个点,统计当前点和其它所有点的斜率,记录斜率最多的次数。
知识点:
1.round(number, digits):digits>0,四舍五入到指定的小数位;digits=0, 四舍五入到最接近的整数;digits<0 ,在小数点左侧进行四舍五入;如果round()函数只有number这个参数,等同于digits=0。四舍五入规则:要求保留位数的后一位<=4,则不进位;要求保留位数的后一位“>=6”,则进位;当精确位后面一位的数字是5的,此时需要看这个5后面是否还有值,如果5后面有值(0忽略),则直接进位,如果5后面没值或值为0,则需要判断5前面的值是偶数还是奇数,如果5前面是偶数,不进位,如果是奇数,进位。
代码:
from itertools import permutations from collections import Counter, defaultdictclass Solution:def maxPoints(self, points: List[List[int]]) -> int:result = 0permutation = defaultdict(list)for p in permutations(points, 2):permutation[tuple(p[0])].append(p[1])for k, v in permutation.items():default = Counter([x1 for x1, y1 in v])[k[0]]result = max(max(list(Counter([round((y1 - k[1]) / (x1 - k[0]), 10) for x1, y1 in v if x1 != k[0]]).values()) + [0]), default, result)return result + 1