leetcode-149-Max Points on a Line

darcrand 發布于2019-07-31 11:03 / 2115人閱讀

"""
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```

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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