149. Max Points on a Line

也找到了一个AC的做法，明天研究

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
import random
import collections
class Solution(object):
    def maxPoints(self, points):
        if len(points)==0: #case for 0 inputs
            return 0
        if len(points)==1: # case for just one point
            return 1
        xls=[]
        yls=[]
        for ii in range(0,len(points)): # case for all  the points are same
            xls.append(points[ii].x)
            yls.append(points[ii].y)
        xset=set(xls)
        yset=set(yls)
        if len(xset)==1 and len(yset)==1:
            return len(points)
        max_points=0
        for i in range (0,100):
            [p1,p2]=random.sample(range(len(points)), 2) # randomly choose two points
            while(points[p1].x==points[p2].x and points[p2].y==points[p1].y ): #make sure two points are different
                [p1,p2]=random.sample(range(len(points)), 2)
            
            X1=points[p1].x
            X2=points[p2].x
            Y1=points[p1].y
            Y2=points[p2].y
            A = Y2 - Y1
            B = X1 - X2
            C=X2*Y1 - X1*Y2  #define the parameters of the line
            temp_num=0
            for j in range(0,len(points)):
                X=points[j].x
                Y=points[j].y
                if A*X+B*Y+C==0: # the error must be 0 to make sure the point is in the line
                    temp_num=temp_num+1
            if temp_num > max_points:
                max_points=temp_num
        
        return max_points

这其实不是一个完美的做法，因为有随机性在里面，过leetcode没问题但不能保证其他，所以，还是遍历最靠谱，改了一下，代码如下：

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
import random
import collections
class Solution(object):
    def maxPoints(self, points):
        if len(points)==0: #case for 0 inputs
            return 0
        if len(points)==1: # case for just one point
            return 1
        xls=[]
        yls=[]
        for ii in range(0,len(points)): # case for all  the points are same
            xls.append(points[ii].x)
            yls.append(points[ii].y)
        xset=set(xls)
        yset=set(yls)
        if len(xset)==1 and len(yset)==1:
            return len(points)
        max_points=0
        for p1 in range(len(points) - 1):
            for p2 in range(p1, len(points)):
                if points[p1].x==points[p2].x and points[p2].y==points[p1].y: #make sure two points are different
                    continue
                X1=points[p1].x
                X2=points[p2].x
                Y1=points[p1].y
                Y2=points[p2].y
                A = Y2 - Y1
                B = X1 - X2
                C=X2*Y1 - X1*Y2  #define the parameters of the line
                temp_num=0
                for j in range(0,len(points)):
                    X=points[j].x
                    Y=points[j].y
                    if A*X+B*Y+C==0: # the error must be 0 to make sure the point is in the line
                        temp_num=temp_num+1
                if temp_num > max_points:
                    max_points=temp_num
        
        return max_points