LeetCode - Max Points on a Line

最近迷上了函数式编程，虽然没系统地学习，但是一直在尝试使用，今天就花了一晚上的时间用函数式编程写了一道 LeetCode，总算是写出来了。

最后有个 BUG 调试了很久，和别人代码的输出比较之后才解决：统计相同坐标出现次数时排序设的函数写错了，41 行原来的代码是points = sorted(points, key=lambda p: p.x，只用了 x 坐标，没有把 y 坐标考虑进去，这样的话 groupby 会把相同的坐标存在两个 group 里（被 groupby 坑了）。

code_0

初用 Python 的函数式编程，可能有以下几个坑要及时闪避：

itertools.groupby 不太适合把 Tuple 转化为一种类似字典的东西，因为你必须先对你的内容进行排序（你需要的是 defaultdict）
在 lambda 中是不能使用复制语句的，换句话就是你不能改变外界的环境（实际上是可以改变，但是稍微有点复杂，可参见 Assignment inside lambda expression in Python - Stack Overflow）
函数！函数！（Every function’s output must only depend on its input.）

代码：

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b
    def __str__(self):
        return "(%d, %d)" % (self.x, self.y)

import sys
import itertools
from collections import defaultdict

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        def ratio(pair):
            p1, p2 = pair
            if p1.x!=p2.x:
                ka=round(p1.y-1.0*(p2.y-p1.y)/(p2.x-p1.x)*p1.x, 3)
                kb=round(1.0*(p2.y-p1.y)/(p2.x-p1.x), 3)
            else:
                ka=round(p1.x-1.0*(p2.x-p1.x)/(p2.y-p1.y)*p1.y, 3)
                kb=None
            return (ka, kb)
        
        def pointRatio(pair):
            return pair[1]
        
        def count(point, group):
            return len(list(filter(lambda x: point in x[0], group)))

        def same(point):
            return (point.x, point.y)

        def countSame(samePointsCount, lines):
            lines = list(lines)
            s = set()
            map(lambda x: s.add(same(x[0][0])) or s.add(same(x[0][1])) and res, lines)
            return reduce(lambda res, x: res+samePointsCount[x], s, 0)

        points = sorted(points, key=lambda p: p.x*2**32+p.y)

        samePointsCount = dict(map(lambda x: (x[0], len(list(x[1]))), itertools.groupby(points, same)))
        points = [Point(x[0], x[1]) for x in samePointsCount.keys()]
        if len(points) == 1:
            return samePointsCount[same(points[0])]
        allPair = list(itertools.combinations(points, 2))
        pairRatio = map(ratio, allPair)
        ratio_tuples = sorted(itertools.izip(allPair, pairRatio), key=pointRatio)

        return reduce(lambda res, y: max(res, countSame(samePointsCount, y[1])), itertools.groupby(ratio_tuples, pointRatio), 0)

s = Solution()
a = [(40,-23),(9,138),(429,115),(50,-17),(-3,80),(-10,33),(5,-21),(-3,80),(-6,-65),(-18,26),(-6,-65),(5,72),(0,77),(-9,86),(10,-2),(-8,85),(21,130),(18,-6),(-18,26),(-1,-15),(10,-2),(8,69),(-4,63),(0,3),(-4,40),(-7,84),(-8,7),(30,154),(16,-5),(6,90),(18,-6),(5,77),(-4,77),(7,-13),(-1,-45),(16,-5),(-9,86),(-16,11),(-7,84),(1,76),(3,77),(10,67),(1,-37),(-10,-81),(4,-11),(-20,13),(-10,77),(6,-17),(-27,2),(-10,-81),(10,-1),(-9,1),(-8,43),(2,2),(2,-21),(3,82),(8,-1),(10,-1),(-9,1),(-12,42),(16,-5),(-5,-61),(20,-7),(9,-35),(10,6),(12,106),(5,-21),(-5,82),(6,71),(-15,34),(-10,87),(-14,-12),(12,106),(-5,82),(-46,-45),(-4,63),(16,-5),(4,1),(-3,-53),(0,-17),(9,98),(-18,26),(-9,86),(2,77),(-2,-49),(1,76),(-3,-38),(-8,7),(-17,-37),(5,72),(10,-37),(-4,-57),(-3,-53),(3,74),(-3,-11),(-8,7),(1,88),(-12,42),(1,-37),(2,77),(-6,77),(5,72),(-4,-57),(-18,-33),(-12,42),(-9,86),(2,77),(-8,77),(-3,77),(9,-42),(16,41),(-29,-37),(0,-41),(-21,18),(-27,-34),(0,77),(3,74),(-7,-69),(-21,18),(27,146),(-20,13),(21,130),(-6,-65),(14,-4),(0,3),(9,-5),(6,-29),(-2,73),(-1,-15),(1,76),(-4,77),(6,-29)]
b = map(lambda x: Point(x[0], x[1]), a)

print s.maxPoints(b)

Yi's Blog

思绪来得快，去得也快

LeetCode - Max Points on a Line

更多链接