475. Heaters

shiyang6017 發布于2019-08-14 17:28 / 2739人閱讀

摘要：題目鏈接現在題都這個風格了額，感覺有的難度。。之后如果找到最小的，開始想到的是用。

475. Heaters

題目鏈接：https://leetcode.com/problems...

現在easy題都這個風格了額，感覺有medium的難度。。
首先sort兩個數組。之后如果找到最小的radius，開始想到的是用2 points。一個i指house的位置，另一個j指向heater，循環的invariant是：house[0, i]已被heater[0, j]覆蓋，現在來看house[i]，如果

在(heater[j] - radius, heater[j] + radius)之間，則更新i++

如果不在，比較abs(heater[j] - house[i])和abs(heater[j+k] - house[i])找到小的那個更新radius，如果abs(heater[j+k] - house[i])小，則更新j+=k, i++

看tag是binary search，這里就是對每一個house的位置，binary search離它最近的兩邊的heater，然后取距離小的那個更新結果。

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        // sort
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int j = 0;
        int radius = 0;
        for(int house : houses) {
            if(Math.abs(heaters[j] - house) <= radius) continue;
            // if not in radius, update radius
            int local = Math.abs(heaters[j] - house);
            // find the j gives the smallest local radius
            while(j + 1 < heaters.length && Math.abs(heaters[j+1] - house) <= local) {
                local = Math.abs(heaters[j+1] - house);
                j++;
            }
            radius = Math.max(local, radius);
        }
        
        return radius;
    }
}

binary search:

public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        // sort
        Arrays.sort(houses);
        Arrays.sort(heaters);

        int radius = 0;
        for(int house : houses) {
            int local = binarySearch(heaters, house);
            radius = Math.max(radius, local);
        }
        
        return radius;
    }
    
    private int binarySearch(int[] heaters, int target) {
        int l = 0, r = heaters.length - 1;
        while(l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(heaters[mid] == target) return 0;
            else if(heaters[mid] < target) l = mid;
            else r = mid;
        }
        return Math.min(Math.abs(target - heaters[l]), Math.abs(target - heaters[r]));
    }
}

GPU云服務器云服務器 Heaters

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66660.html

走進docker(05)：docker在本地如何管理image（鏡像）?

摘要：里面可以通過等方式得到一個，得到之后在本地是怎么存儲的呢本篇將以為例，簡述的獲取和存儲方式。鏡像相關的配置里面和有關的目錄為，里面存放著的所有信息，可以通過下面這個的啟動參數來修改這個目錄的路徑。 docker里面可以通過docker pull、docker build、docker commit、docker load、docker import等方式得到一個image，得到imag...

gaosboy 2019-06-28 15:51 評論0 收藏0
容器最大盛水量

摘要：容器最大盛水量給定個非負整數，，，，其中每個表示坐標，處的點。找到兩條線，它們與軸一起形成一個容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 給定n個非負整數a1，a2，...，an，其中每個表示坐標（i，ai）處的點。繪制n條垂直線，使得線i的兩個端點在（i，ai）和（i，0）處。找到兩條線，它們與x軸一起形成一個容器，使得容器...

luckyw 2019-07-25 12:04 評論0 收藏0
簡單說 CSS中的mask—好好利用mask-image

摘要：說明中的屬性允許用戶屏蔽或剪裁特定點的圖像來實現，部分或完全隱藏某個元素的可見性。好吧，這個概念可能有點不好理解，先看圖。說明 CSS中的mask屬性允許用戶屏蔽或剪裁特定點的圖像來實現，部分或完全隱藏某個元素的可見性。好吧，這個概念可能有點不好理解，先看圖。 showImg(https://segmentfault.com/img/bVXPSW?w=919&h=136);...

desdik 2019-08-21 17:24 評論0 收藏0
簡單說 CSS中的mask—好好利用mask-image

摘要：說明中的屬性允許用戶屏蔽或剪裁特定點的圖像來實現，部分或完全隱藏某個元素的可見性。好吧，這個概念可能有點不好理解，先看圖。說明 CSS中的mask屬性允許用戶屏蔽或剪裁特定點的圖像來實現，部分或完全隱藏某個元素的可見性。好吧，這個概念可能有點不好理解，先看圖。 showImg(https://segmentfault.com/img/bVXPSW?w=919&h=136);...

ixlei 2019-08-01 17:55 評論0 收藏0