LeetCode刷题实战475:供暖器
Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.
Every house can be warmed, as long as the house is within the heater's warm radius range.
Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.
Notice that all the heaters follow your radius standard, and the warm radius will the same.
示例
示例 1:
输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。
示例 2:
输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。
示例 3:
输入:houses = [1,5], heaters = [2]
输出:3
解题
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int ans=-1;
for(int house:houses){
ans=Math.max(ans,findMinDest(house,heaters));
}
return ans;
}
private int findMinDest(int house,int[] heaters){
int len=heaters.length-1;
if(house>=heaters[len]) return (house-heaters[len]);
if(house<=heaters[0]) return (heaters[0]-house);
int des=Integer.MAX_VALUE;
int left=0;
int right=heaters.length-1;
while(left<=right){
int mid=left+((right-left)>>1);//这个地方当时括号错了,调了半天。
if(heaters[mid]==house) return 0;
if(heaters[mid]//如果当前house>heater[mid],那我们向右缩小范围
des=Math.min(des,Math.abs(house-heaters[mid]));
left=mid+1;
}else{
//当前house
des=Math.min(des,Math.abs(house-heaters[mid]));
right=mid-1;
}
}
return des;
}
}
LeetCode刷题实战462:最少移动次数使数组元素相等 II
LeetCode刷题实战470:用 Rand7() 实现 Rand10()