Python程式：查詢照亮街道上所有房屋的最小半徑

假設我們有一個名為nums的數字列表，代表一維線上房屋的位置。現在考慮我們可以將3個路燈放在線上的任何位置，位置為x的路燈將照亮[x - r, x + r]範圍內的所有房屋（包含端點）。我們必須找到照亮所有房屋所需的最小r。

因此，如果輸入類似於nums = [4,5,6,7]，則輸出將為0.5，因為我們可以將燈放置在4.5、5.5和6.5處，所以r = 0.5。因此，這三盞燈可以照亮所有4個房屋。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式valid()。這將接收r

  • last_location := nums[0] + r

  • count := 1

  • 對於範圍從0到nums大小的i，執行：

    • val := nums[i]

    • 如果 val - last_location > r，則

      • count := count + 1

      • last_location := val + r

  • 當count <= 3時返回true，否則返回false

  • 從主方法執行以下操作：

  • 對列表nums進行排序

  • left := 0

  • right := nums的最後一個元素

  • res := inf

  • itr := 0

  • 當 left <= right 且 itr < 20 時，執行：

    • mid := left +(right - left) / 2

    • 如果valid(mid)為true，則

      • res := res和mid的最小值

      • right := mid

    • 否則，

      • left := mid

      • itr := itr + 1

  • 返回res

示例

讓我們看看下面的實現以更好地理解：

線上演示

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))

輸入

[4,5,6,7]

輸出

0.5

更新於：2020年12月22日

瀏覽量：586

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告