杭州建设监理协会网站,网站制作过程中碰到的问题,海外留学网站建设方案,顺企网上海网站建设Max Points on a Line 要点#xff1a;这题暴力解是用任何两点确定一条直线#xff0c;然后对其他点检查是否共线#xff0c;显然#xff0c;这里没用空间来存储之前的检查结果#xff0c;所以time complexity是O(n^3)。这题的难点是如何存储从而实现O(n^2)解。思路是另一… Max Points on a Line 要点这题暴力解是用任何两点确定一条直线然后对其他点检查是否共线显然这里没用空间来存储之前的检查结果所以time complexity是O(n^3)。这题的难点是如何存储从而实现O(n^2)解。思路是另一种确定一条直线的方法是一点和theta所以theta可以作为map的key。每次内循环就是检查对于该点下最多共线的点数。 错误点 双循环loop所有pair的方法inner loop要找外层index的下一个hashmap是local的不是global的localmax1: 这样1个点或者都是相同点可以passtheta的计算对于java因为坐标是int必须先用(double) cast及时theta类型是double。而python没有类型用float(x-x0)即可# Definition for a point.
# class Point(object):
# def __init__(self, a0, b0):
# self.x a
# self.y bclass Solution(object):def maxPoints(self, points)::type points: List[Point]:rtype: intmaxp 0for i in range(len(points)):localmax 1hmap {}x,y points[i].x,points[i].ysame 0for j in range(i1, len(points)):px,py points[j].x,points[j].yif px-x0:if pyy:same1continueelse:theta float(inf)else:theta (py-y)/float(px-x)print i,j, thetaif theta not in hmap:hmap[theta]2else:hmap[theta]1if hmap[theta]localmax:localmax hmap[theta]if localmaxsamemaxp:maxp localmaxsamereturn maxp 转载于:https://www.cnblogs.com/absolute/p/5560412.html
