热99视频,人人爱天天做,99re伊人,欧美操,午夜精品人妻无码,狠狠操B,舔逼乳头大片,久久亚洲免费视频

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?供暖器，我們先來看題面：

https://leetcode-cn.com/problems/heaters/

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.

冬季已經(jīng)來臨。你的任務(wù)是設(shè)計(jì)一個有固定加熱半徑的供暖器向所有房屋供暖。

在加熱器的加熱半徑范圍內(nèi)的每個房屋都可以獲得供暖。

現(xiàn)在，給出位于一條水平線上的房屋 houses 和供暖器 heaters 的位置，請你找出并返回可以覆蓋所有房屋的最小加熱半徑。

說明：所有供暖器都遵循你的半徑標(biāo)準(zhǔn)，加熱的半徑也一樣。

示例? ? ? ? ? ? ? ? ? ? ? ? ?

示例 1:
輸入: houses = [1,2,3], heaters = [2]
輸出: 1
解釋: 僅在位置2上有一個供暖器。如果我們將加熱半徑設(shè)為1，那么所有房屋就都能得到供暖。

示例 2:
輸入: houses = [1,2,3,4], heaters = [1,4]
輸出: 1
解釋: 在位置1, 4上有兩個供暖器。我們需要將加熱半徑設(shè)為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);//這個地方當(dāng)時括號錯了，調(diào)了半天。
????????????if(heaters[mid]==house) return?0;
????????????if(heaters[mid]??????????????//如果當(dāng)前house>heater[mid],那我們向右縮小范圍
????????????????des=Math.min(des,Math.abs(house-heaters[mid]));
????????????????left=mid+1;
????????????}else{
????????????//當(dāng)前house
????????????????des=Math.min(des,Math.abs(house-heaters[mid]));
????????????????right=mid-1;
????????????} 
????????}
????????return?des;
????}
}