149. Max Points on a Line

Loading...LeetCode

判断共线也是三点间关系，可以确定两点然后遍历所有第三点来找解，这个有跟3Sum类似的地方，但不同的是这边不是可以按照大小关系排列的array，而是cordinates，只能三点全部都做遍历，时间复杂度近似n**3.

15. 3Sum

本来想通过记录斜率来写个n**2的解法，结果因为python的浮点数问题，某些test case就是过不了，懒得整了.

Python

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        res = 0
        n = len(points)
        if n <= 2: return n
        # 确认第一点
        for i in range(n):
            x1, y1 = points[i]
            repeat = 1
            # 第二点，直接从 i 后面一个开始选起，节约计算
            for j in range(i+1, n):
                x2, y2 = points[j]
                line = 0
                # input里有重合点，需要另算重合点的计数
                if x1 == x2 and y1 == y2: 
                    repeat += 1
                    continue
                # i, j 两点就已经确定一条直线了
                # 确认了直线，第三点就只需要判断是否落在直线上
                for k in range(n):
                    x3, y3 = points[k]
                    if (x1-x3)*(y2-y3) == (x2-x3)*(y1-y3): line += 1
                        
                res = max(line, res)
                
            res = max(repeat, res)
            
        return res

浮点数问题通过不了

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2: return n
        
        res = 0
        
        for i in range(n):
            x1, y1 = points[i]
            memo = collections.defaultdict(int)
            repeat, count = 0, 0
            
            for j in range(i+1, n):
                x2, y2 = points[j]
                line = 0
                if x1 == x2 and y1 == y2: repeat += 1
                else:
                    slope = (x2-x1)/(y2-y1) if y2 != y1 else 'inf'
                    memo[slope] += 1
                    count = max(memo[slope], count)
                
            res = max(res, count+1+repeat)
            
        return res