国产探花免费观看_亚洲丰满少妇自慰呻吟_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
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 庆阳市| 昌平区| 砚山县| 手机| 鄂伦春自治旗| 任丘市| 昌乐县| 句容市| 苏尼特右旗| 茶陵县| 略阳县| 甘南县| 长治县| 射洪县| 原阳县| 巴南区| 页游| 乳源| 农安县| 克什克腾旗| 平和县| 密云县| 瓦房店市| 三穗县| 浙江省| 靖江市| 阿巴嘎旗| 双峰县| 盐边县| 炉霍县| 汶川县| 通化县| 潼南县| 蒙山县| 台东市| 阳高县| 揭东县| 海口市| 汝阳县| 封开县| 汝阳县|