leetcode-149-Max Points on a Line

darcrand 发布于2019-07-31 11:03 / 2096人阅读

"""
Given n points on a 2D plane,
find the maximum number of points that lie on the same straight line.

"""

from decimal import Decimal

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

class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        if not points:
            return 0
        # xs=[point.x for point in points]
        # ys=[point.y for point in points]
        length=len(points)
        if length==1:
            return 1
        counter=0
        for ip in range(length-1):

            kdict={"i":1}
            same=0
            for jp in range(ip+1,length):
                if points[jp].x==points[ip].x and points[ip].y==points[jp].y:
                    same+=1
                elif points[jp].x==points[ip].x:
                    kdict["i"]+=1
                else:
                    k=Decimal(points[jp].y-points[ip].y*Decimal(1.0))/Decimal(points[jp].x-points[ip].x)
                    print(k)
                    if k not in kdict.keys():
                        kdict[k]=2
                    else:
                        kdict[k]+=1

            counter=max(counter,max(kdict.values())+same)
        # print(counter)
        return counter
if __name__=="__main__":
    st=Solution()
    points=[Point(i,j) for i in range(9) for j in range(3,12)]
    points=[Point(1,2),Point(1,2),Point(1,2),Point(3,6),Point(2,4),Point(4,8),Point(5,10),]
    # points=[Point(0,0)]
    # points=[Point(0,0),Point(1,0)]

    points=[Point(0,0),Point(1,1),Point(1,-1)]
    points=[Point(0,0),Point(94911151,94911150),Point(94911152,94911151)]

    out=st.maxPoints(points)
    print(out)
    float```

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44560.html

[LintCode] Max Points on a Line

摘要：两次循环对中第个和第个进行比较设置重复点数，相同斜率点数。内部循环每次结束后更新和点相同斜率的点的最大数目。外部循环每次更新为之前结果和本次循环所得的较大值。重点一以一个点为参照求其他点连线的斜率，不需要计算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...

bingo 2019-08-14 15:14 评论0 收藏0
[Leetcode] Max Points on a Line 线上最大点数

摘要：哈希表复杂度时间空间思路一个点加一个斜率，就可以唯一的确定一条直线。这里，我们用哈希表，以斜率为，记录有多少重复直线。注意哈希表的为，但是可以有正和负的，而且不一样。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same stra...

ernest.wang 2019-08-14 12:49 评论0 收藏0
[Leetcode] Max Points on a Line 直线上最多的点数

摘要：分子分母同时除以他们的最大公约数即可得到最简分数，一般求的是两个正整数的。这道题和有可能是，分别表示与轴或轴平行的斜率注意不能同时为表示同一个点没有意义，所以这道题我们规定取值范围。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...

张宪坤 2019-08-14 14:05 评论0 收藏0
LeetCode 4

摘要：这个题的思路就是找数组里的两个点，用这两个点来做一条直线，然后看数组里的点都在直线上不，我用的是两点式，需要考虑两个点或坐标相同的特殊情况。 Max Points on a Line https://oj.leetcode.com/problems/max-points-on-a-line/ Given n points on a 2D plane, find the maximu...

zhkai 2019-08-14 11:46 评论0 收藏0