Clean python code


  • 5

    This problem has two points to note:

    • point in points may be duplicate.
    • use a*y + b*x + c = 0 to represent a line, not y = k*x + b, because k and b may be float number, and float numbers can't be compared with =. Two equal key in hash table representing line may differ.

    .

    class Solution(object):
        def gcd(self, a, b):
            while b:
                a, b = b, a % b
            return a
    
        def maxPoints(self, points):
            if not points:
                return 0
    
            points = map(lambda p: (p.x, p.y), points)
    
            counter, points, lines = (
                collections.Counter(points), list(set(points)),
                collections.defaultdict(set))
    
            for i in xrange(len(points)):
                for j in xrange(i + 1, len(points)):
                    (x1, y1), (x2, y2) = points[i], points[j]
    
                    a, b, c = x1 - x2, y2 - y1, x2 * y1 - x1 * y2
                    if a < 0 or a == 0 and b < 0:
                        a, b, c = -a, -b, -c
    
                    gcd = self.gcd(self.gcd(abs(a), abs(b)), abs(c))
                    lines[(a / gcd, b / gcd, c / gcd)] |= {points[i], points[j]}
    
            return max([
                sum([counter[p] for p in ps])
                for ps in lines.values()
            ] + counter.values())

  • 1

    @shiyanhui
    It is vary kind of you to share your idea, and the code works well.
    However it makes me a little confused, when it comes to
    a, b, c = x1 - x2, y2 - y1, x2 * y1 - x1 * y2

    Here is my addition for this to make it clear.
    If there are two points (x1, y1), (x2, y2) [x1 != x2, y1 != y2],
    and they are in line (y - y1) / (y2 - y1) = (x - x1) / (x2 - x1) ==> (y2 - y1)x + (x1 - x2)y + y1x2 - x1y2 = 0
    As a result,

    class Solution(object):
        def maxPoints(self, points):
            """
            :type points: List[Point]
            :rtype: int
            """
            from collections import defaultdict
            result, lens, points = 0, len(points), map(lambda p: (p.x, p.y), points)                
            for i in range(lens):
                x1, y1 = points[i]
                same, lines = 1, defaultdict(int)
                for j in range(i+1, lens):
                    x2, y2 = points[j]
                    if x1 == x2 and y1 == y2:
                        same += 1  
                    else:
                        if y2 < y1 or y2 == y2 and x1 < x2:
                            a, b, c = - y2 + y1, - x1 + x2, - y1 * x2 + y2 * x1
                        else:    
                            a, b, c = y2 - y1, x1 - x2, y1 * x2 - y2 * x1
                        rate = self.gcb(self.gcb(a, b), c)     
                        lines[(a / rate, b / rate, c /rate)] += 1 
                result = max(result, (max(lines.values()) if lines.values() else 0) + same)
            return result    
    
        def gcb(self, a, b):
            while b:
                a, b = b, a % b
            return a 
    

    BTW, the input [[0,0],[94911151,94911150],[94911152,94911151]] will force you to deal with y = k*x + b more carefully.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.