สมมติว่าเรามีรายการพิกัด แต่ละพิกัดมีค่า x และ y สองค่า ซึ่งแสดงถึงจุดบนระนาบคาร์ทีเซียน ตอนนี้หาจำนวนคะแนนสูงสุดที่อยู่บนเส้นบางเส้น
ดังนั้น ถ้าอินพุตเป็นเหมือนพิกัด =[[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
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของรายการคะแนน ทำ
-
(x1, y1) :=คะแนน[i]
-
ความลาดชัน :=แผนที่ใหม่
-
เหมือนเดิม :=1
-
สำหรับ j ในช่วง i + 1 ถึงขนาดของจุด ทำ
-
(x2, y2) :=คะแนน[j]
-
ถ้า x2 เหมือนกับ x1 แล้ว
-
ลาด[inf] :=1 + (ลาด[inf] ถ้าออกมิฉะนั้น 0)
-
-
มิฉะนั้นเมื่อ x1 เหมือนกับ x2 และ y1 เหมือนกับ y2 ดังนั้น
-
เหมือนกัน :=เหมือนกัน + 1
-
-
มิฉะนั้น
-
ความชัน :=(y2 - y1) /(x2 - x1)
-
ลาด[ลาด] :=1 + (ลาด[ลาดชัน] ถ้าออกมิฉะนั้น 0)
-
-
-
ถ้าเนินไม่ว่าง
-
res :=สูงสุดของ 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
