資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python中的加熱器
假設我們必須設計一個具有固定加熱半徑的標準加熱器來溫暖所有房屋。現在，我們給出了房屋和加熱器在水平線上的位置，我們必須找到加熱器的最小半徑，以便所有房屋都能被這些加熱器覆蓋。因此，我們將分別提供房屋和加熱器，我們的預期輸出將是加熱器的最小半徑標準。
因此，如果輸入類似於[1,2,3,4],[1,4]，則輸出將為1，因為兩個加熱器分別放置在位置1和4。我們必須使用半徑1，然後所有房屋都可以被加熱。
為了解決這個問題，我們將遵循以下步驟：
對房屋列表進行排序
對加熱器列表進行排序
res := 一個大小與房屋陣列相同，並用inf填充的陣列
對於範圍從0到房屋大小的i，執行以下操作：
h := houses[i]
ind := 將h插入加熱器中使其列表保持排序的最左索引
如果ind與加熱器的大小相同，則
res[i] := res[i]，|h - heaters[-1]| 的最小值
否則，當ind為0時，則
res[i] := res[i]，|h - heaters[0]| 的最小值
否則，
res[i] := res[i]，|h - heaters[ind]|，|h - heaters[ind-1]| 的最小值
返回res的最大值
示例
讓我們看看下面的實現，以便更好地理解：
from bisect import bisect_left
class Solution:
def findRadius(self, houses, heaters):
houses.sort()
heaters.sort()
res = [float('inf')]*len(houses)
for i in range(len(houses)):
h = houses[i]
ind = bisect_left(heaters, h)
if ind==len(heaters):
res[i] = min(res[i], abs(h - heaters[-1]))
elif ind == 0:
res[i] = min(res[i], abs(h - heaters[0]))
else:
res[i] = min(res[i], abs(h - heaters[ind]), abs(h - heaters[ind-1]))
return max(res)
ob = Solution()
print(ob.findRadius([1,2,3,4],[1,4]))輸入
[1,2,3,4],[1,4]
輸出
1
更新於：2020年6月10日
213 次瀏覽
廣告