首页 > 代码库 > 【leetcode】Max Points on a Line (python)
【leetcode】Max Points on a Line (python)
给定一个点,除该点之外的其他所有点中,与该点的关系要么是共线,要么就是共点,也就是两点重合。
共线有三种情况:水平共线,垂直共线,倾斜的共线。合并下这三种情况就是斜率存在的共线和斜率不存在的共线。
那么我们的任务就是针对每个点,找出与其共线的这些情况中,共线最多的点的个数。
注意:最终的结果别忘了加上共点的个数。
class Solution: def maxPoints(self, points ): if len( points ) <= 1: return len( points ) maxpoints = 1 for i in range( len( points ) - 1): vitical = 1 slops = { } samePoints = 0 curmax = 1 for j in range( i + 1, len( points ) ): if points[ i ].x == points[ j ].x and points[ i ].y == points[ j ].y: samePoints += 1 continue elif points[ i ].x == points[ j ].x: vitical += 1 else: slop = ( points[ j ].y - points[ i ].y ) * 1.0 / ( points[ j ].x - points[i].x ) slops.setdefault( slop, 1 ) slops[ slop ] += 1 if slops[ slop ] > curmax: curmax = slops[ slop ] maxpoints = max( max( curmax, vitical ) + samePoints, maxpoints ) return maxpoints
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。