資訊專欄INFORMATION COLUMN
"""
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```
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44560.html
摘要：兩次循環(huán)對中第個和第個進行比較設(shè)置重復(fù)點數(shù)，相同斜率點數(shù)。內(nèi)部循環(huán)每次結(jié)束后更新和點相同斜率的點的最大數(shù)目。外部循環(huán)每次更新為之前結(jié)果和本次循環(huán)所得的較大值。重點一以一個點為參照求其他點連線的斜率，不需要計算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...
摘要：哈希表復(fù)雜度時間空間思路一個點加一個斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復(fù)直線。注意哈希表的為，但是可以有正和負的，而且不一樣。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same stra...
摘要：分子分母同時除以他們的最大公約數(shù)即可得到最簡分數(shù)，一般求的是兩個正整數(shù)的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時為表示同一個點沒有意義，所以這道題我們規(guī)定取值范圍。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...
摘要：這個題的思路就是找數(shù)組里的兩個點，用這兩個點來做一條直線，然后看數(shù)組里的點都在直線上不，我用的是兩點式，需要考慮兩個點或坐標相同的特殊情況。 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...
閱讀 1344·2021-09-04 16:40
閱讀 3467·2021-07-28 00:13
閱讀 2893·2019-08-30 11:19
閱讀 2625·2019-08-29 12:29
閱讀 3179·2019-08-29 12:24
閱讀 1132·2019-08-26 13:28
閱讀 2409·2019-08-26 12:01
閱讀 3457·2019-08-26 11:35
