数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
广告