Candy (Python)
Interleaving String (Python)

Max Points on a Line (Python)

kitt posted @ 2014年2月12日 00:40 in LeetCode , 1889 阅读

计算每两点之间的斜率,找最大值,要注意同一个坐标多次出现的情况。

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        length = len(points)
        if length < 3: return length
        res = -1
        for i in xrange(length):
            slope = {'inf': 0}
            samePointNum = 1
            for j in xrange(length):
                if i == j: 
                    continue
                if points[i].x == points[j].x and points[i].y != points[j].y:
                    slope['inf'] += 1
                elif points[i].x != points[j].x:
                    k = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x)
                    slope[k] = 1 if k not in slope else slope[k] + 1
                else:
                    samePointNum += 1
            res = max(res, max(slope.values()) + samePointNum)
        return res

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter