Giả sử chúng ta có một danh sách các số được gọi là nums đại diện cho vị trí của các ngôi nhà trên một đường 1 chiều. Bây giờ, hãy xem xét chúng ta có 3 đèn đường mà chúng ta có thể đặt ở bất kỳ vị trí nào trên đường thẳng và một đèn ở vị trí x chiếu sáng tất cả các ngôi nhà trong phạm vi [x - r, x + r], bao gồm cả. Chúng tôi phải tìm ra r nhỏ nhất cần thiết để thắp sáng tất cả các ngôi nhà.
Vì vậy, nếu đầu vào là nums =[4,5,6,7], thì đầu ra sẽ là 0,5, vì chúng ta có thể đặt các đèn trên 4,5, 5,5 và 6,5 nên r =0,5. Như vậy ba ngọn đèn này có thể thắp sáng cả 4 ngôi nhà.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm hợp lệ (). Điều này sẽ mất r
-
last_location:=nums [0] + r
-
đếm:=1
-
đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
-
val:=nums [i]
-
if val - last_location> r, then
-
count:=count + 1
-
last_location:=val + r
-
-
-
trả về true khi đếm <=3, ngược lại là false
-
Từ phương thức chính, hãy làm như sau -
-
sắp xếp số lượng danh sách
-
trái:=0
-
right:=phần tử cuối cùng của nums
-
res:=inf
-
itr:=0
-
trong khi left <=right và itr <20, thực hiện
-
giữa:=left + (phải - trái) / 2
-
nếu hợp lệ (giữa) là true, thì
-
res:=tối thiểu là res và mid
-
right:=mid
-
-
nếu không,
-
left:=mid
-
itr:=itr + 1
-
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution:
def solve(self, nums):
def valid(r):
last_location = nums[0] + r
count = 1
for i in range(len(nums)):
val = nums[i]
if val - last_location > r:
count += 1
last_location = val + r
return count <= 3
nums.sort()
left = 0
right = nums[-1]
res = float("inf")
itr = 0
while left <= right and itr < 20:
mid = left + (right - left) / 2
if valid(mid):
res = min(res, mid)
right = mid
else:
left = mid
itr += 1
return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums)) Đầu vào
[4,5,6,7]
Đầu ra
0.5