[LeetCode]题解（python）：149-Max Points on a Line

题目来源：

　　https://leetcode.com/problems/max-points-on-a-line/

题意分析：

　　在一个2D的板上面有很多个点，判断最多有多少个点在同一条直线上。

题目思路：

　　这里我们可以用斜率来记录两条边是否在同一条直线。如果考虑再细一点，由于double有精度的问题，斜率最后用分数来表示。

代码（python）：

# Definition for a point.

# class Point(object):

#     def __init__(self, a=0, b=0):

#         self.x = a

#         self.y = b

class Solution(object):

    def maxPoints(self, points):

        """

        :type points: List[Point]

        :rtype: int

        """

        size = len(points)

        if size  < 3:

            return size

        ans = 0

        for i in range(size):

            d = {'inf':0}

            samePoint = 1

            for j in range(size):

                if i == j:

                    continue

                elif points[i].x == points[j].x and points[i].y != points[j].y:

                    d['inf'] += 1

                elif points[i].x != points[j].x:

                    k = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x)

                    if k in d:

                        d[k] += 1

                    else:

                        d[k] = 1

                else:

                    samePoint += 1

            ans = max(ans,max(d.values()) + samePoint)

        return ans

巴特西

[LeetCode]题解（python）：149-Max Points on a Line

最新文章

热门文章