国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

475. Heaters

2019-11-08 03:09:01
字體:
來源:轉載
供稿:網友

該題目簡而言之,就是找出每個house的min heater(距離最近的heater),算出radius(半徑),再找出所有house對應的radius中的最大值,即為標準供熱半徑。

binary search可以找出有序數組中需要查找的數字

簡單舉例: houses[14] heaters[1,8,10,20,32] 只有一間屋子,位于14這個位置,左側最近的heater位于10,右側最近的heater位于20,min(14-10,20,14)=4,所以14這件屋子需要供熱的話,radius=4即可 (這是最基本的思路)

下述算法給出的是對基本算法略微改進的算法,希望讀者在基本思路的基礎上去理解下述算法。


class Solution(object): def findRadius(self, houses, heaters): """ :type houses: List[int] :type heaters: List[int] :rtype: int """ heaters = sorted(heaters) houses = sorted(houses) i = radius = 0 for house in houses: while i < len(heaters) - 1 and house > heaters[i]: i += 1 if i != 0: radius = max(radius, min(house - heaters[i - 1],abs(house - heaters[i]))) else: radius = max(abs(house - heaters[0]), radius) return radius
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 西平县| 鄯善县| 保靖县| 聂拉木县| 望奎县| 达拉特旗| 高平市| 大邑县| 宜兰市| 岑溪市| 武威市| 沙田区| 多伦县| 永和县| 塔河县| 双江| 额济纳旗| 鸡泽县| 中牟县| 扬中市| 墨脱县| 台南市| 高阳县| 扶沟县| 尼勒克县| 项城市| 舞钢市| 南岸区| 德阳市| 铜梁县| 平远县| 洪江市| 松江区| 宜章县| 东平县| 景谷| 如东县| 泉州市| 沂水县| 屏南县| 德阳市|