首页 > 代码库 > 【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