python-3.x - 使用 python 3 在一条线上的最大点数

Question

算法题：给定二维平面上的 n 个点，找出位于同一直线上的最大点数。

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

工作 python 3 代码如下： 想知道片段 1d[slope] = d.get(slope, 1) + 1正在工作

但是为什么即使片段 1 和 2 相同，此片段 2 也无法正常工作，例如 2

                    if slope in d:
                         d[slope] += 1
                     else:
                         d[slope] = 1

    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b) 
    
    def get_slope(self, p1, p2):
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]
        
        c = self.gcd(dx, dy)
        
        dx /= c
        dy /= c
        return str(dy) + "/" + str(dx) 
    
    def is_same_points(self, p1:List[int], p2:List[int]): 
        return p1[0] == p2[0] and p1[1] == p2[1]
    
    def maxPoints(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        
        n = len(points)
 
        count = 1
        
        for i in range(0, n):
            d = {}
            duped = 0
            localmax = 1
            p1 = points[i]

            for j in range(i+1, n):
                p2 = points[j]
                
                if self.is_same_points(p1, p2):
                    duped += 1
                else:
                    slope = self.get_slope(p1, p2)


                    # 1) not work: output is 3 in example 2
                    # if slope in d:
                    #     d[slope] += 1
                    # else:
                    #     d[slope] = 1
                    
                    # 2) works: correct output 4 for example 2
                    d[slope] = d.get(slope, 1) + 1

                    localmax = max(localmax, d[slope]);
                   
            count = max(count, localmax + duped)
                    
        return count

标签： python-3.xalgorithm

Answer 1

有趣的问题和很好的解决方案。

注释掉的代码不起作用的原因是：

else:
    d[slope] = 1  ## correct would be d[slope] = 2

每 2 个点都在同一条线上，前两个 p1 p2 只计算一个点，因此在最终答案中你会少一个点。