【leetcode】Max Points on a Line （python)
浏览数：35 /
时间：2015年06月08日
给定一个点，除该点之外的其他所有点中，与该点的关系要么是共线，要么就是共点，也就是两点重合。
共线有三种情况：水平共线，垂直共线，倾斜的共线。合并下这三种情况就是斜率存在的共线和斜率不存在的共线。
那么我们的任务就是针对每个点，找出与其共线的这些情况中，共线最多的点的个数。
注意：最终的结果别忘了加上共点的个数。
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郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
