475. Heaters

shiyang6017 发布于2019-08-14 17:28 / 2593人阅读

摘要：题目链接现在题都这个风格了额，感觉有的难度。。之后如果找到最小的，开始想到的是用。

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]));
    }
}

私有云海外云主机 Heaters

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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