資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目鏈接現(xiàn)在題都這個(gè)風(fēng)格了額，感覺(jué)有的難度。。之后如果找到最小的，開(kāi)始想到的是用。
475. Heaters
題目鏈接：https://leetcode.com/problems...
現(xiàn)在easy題都這個(gè)風(fēng)格了額，感覺(jué)有medium的難度。。
首先sort兩個(gè)數(shù)組。之后如果找到最小的radius，開(kāi)始想到的是用2 points。一個(gè)i指house的位置，另一個(gè)j指向heater，循環(huán)的invariant是：house[0, i]已被heater[0, j]覆蓋，現(xiàn)在來(lái)看house[i]，如果
在(heater[j] - radius, heater[j] + radius)之間，則更新i++
如果不在，比較abs(heater[j] - house[i])和abs(heater[j+k] - house[i])找到小的那個(gè)更新radius，如果abs(heater[j+k] - house[i])小，則更新j+=k, i++
看tag是binary search，這里就是對(duì)每一個(gè)house的位置，binary search離它最近的兩邊的heater，然后取距離小的那個(gè)更新結(jié)果。
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]));
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66660.html
摘要：里面可以通過(guò)等方式得到一個(gè)，得到之后在本地是怎么存儲(chǔ)的呢本篇將以為例，簡(jiǎn)述的獲取和存儲(chǔ)方式。鏡像相關(guān)的配置里面和有關(guān)的目錄為，里面存放著的所有信息，可以通過(guò)下面這個(gè)的啟動(dòng)參數(shù)來(lái)修改這個(gè)目錄的路徑。 docker里面可以通過(guò)docker pull、docker build、docker commit、docker load、docker import等方式得到一個(gè)image，得到imag...
摘要：容器最大盛水量給定個(gè)非負(fù)整數(shù)，，，，其中每個(gè)表示坐標(biāo)，處的點(diǎn)。找到兩條線(xiàn)，它們與軸一起形成一個(gè)容器，使得容器含有最多的水。 容器最大盛水量 Container With Most Water 給定n個(gè)非負(fù)整數(shù)a1，a2，...，an，其中每個(gè)表示坐標(biāo)（i，ai）處的點(diǎn)。 繪制n條垂直線(xiàn)，使得線(xiàn)i的兩個(gè)端點(diǎn)在（i，ai）和（i，0）處。 找到兩條線(xiàn)，它們與x軸一起形成一個(gè)容器，使得容器...
摘要：說(shuō)明中的屬性允許用戶(hù)屏蔽或剪裁特定點(diǎn)的圖像來(lái)實(shí)現(xiàn)，部分或完全隱藏某個(gè)元素的可見(jiàn)性。好吧，這個(gè)概念可能有點(diǎn)不好理解，先看圖。 說(shuō)明 CSS中的mask屬性允許用戶(hù)屏蔽或剪裁特定點(diǎn)的圖像來(lái)實(shí)現(xiàn)，部分或完全隱藏某個(gè)元素的可見(jiàn)性。 好吧，這個(gè)概念可能有點(diǎn)不好理解，先看圖。 showImg(https://segmentfault.com/img/bVXPSW?w=919&h=136);...
摘要：說(shuō)明中的屬性允許用戶(hù)屏蔽或剪裁特定點(diǎn)的圖像來(lái)實(shí)現(xiàn)，部分或完全隱藏某個(gè)元素的可見(jiàn)性。好吧，這個(gè)概念可能有點(diǎn)不好理解，先看圖。 說(shuō)明 CSS中的mask屬性允許用戶(hù)屏蔽或剪裁特定點(diǎn)的圖像來(lái)實(shí)現(xiàn)，部分或完全隱藏某個(gè)元素的可見(jiàn)性。 好吧，這個(gè)概念可能有點(diǎn)不好理解，先看圖。 showImg(https://segmentfault.com/img/bVXPSW?w=919&h=136);...
閱讀 3218·2023-04-25 18:22
閱讀 2510·2021-11-17 09:33
閱讀 3621·2021-10-11 10:59
閱讀 3306·2021-09-22 15:50
閱讀 2939·2021-09-10 10:50
閱讀 921·2019-08-30 15:53
閱讀 508·2019-08-29 11:21
閱讀 3043·2019-08-26 13:58
