資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Python程式：計算位於同一條直線上的點的數量
假設我們有一組座標。每個座標有兩個值x和y，代表笛卡爾平面上的一個點。現在找到位於同一條直線上的點的最大數量。
因此，如果輸入類似於coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]，則輸出為4，因為點[1, 1]，[2, 2]，[6, 6]，[7, 7]位於同一條直線上。
為了解決這個問題，我們將遵循以下步驟：
res := 0
對於 i 從 0 到 points 列表的大小，執行：
(x1, y1) := points[i]
slopes := 一個新的對映
same := 1
對於 j 從 i + 1 到 points 列表的大小，執行：
(x2, y2) := points[j]
如果 x2 等於 x1，則
slopes[inf] := 1 + (如果 slopes[inf] 存在，則為 slopes[inf]，否則為 0)
否則，如果 x1 等於 x2 且 y1 等於 y2，則
same := same + 1
否則，
slope := (y2 - y1) / (x2 - x1)
slopes[slope] := 1 + (如果 slopes[slope] 存在，則為 slopes[slope]，否則為 0)
如果 slopes 不為空，則
res := res 和 (same + slopes 所有值的列表的最大值) 中的最大值
返回 res
示例
讓我們看看下面的實現來更好地理解：
class Solution:
def solve(self, points):
res = 0
for i in range(len(points)):
x1, y1 = points[i][0], points[i][1]
slopes = {}
same = 1
for j in range(i + 1, len(points)):
x2, y2 = points[j][0], points[j][1]
if x2 == x1:
slopes[float("inf")] = slopes.get(float("inf"), 0) + 1
elif x1 == x2 and y1 == y2:
same += 1
else:
slope = (y2 - y1) / (x2 - x1)
slopes[slope] = slopes.get(slope, 0) + 1
if slopes:
res = max(res, same + max(slopes.values()))
return res
ob = Solution()
coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
print(ob.solve(coordinates))輸入
[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
輸出
4
更新於：2020-12-22
567 次瀏覽
廣告