leetcode-475-Heaters

题目描述:

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters' warm radius range, it can be warmed.
  4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

要完成的函数:

int findRadius(vector<int>& houses, vector<int>& heaters) 

说明:

1、这道题目给定两个vector,一个存储了房屋的位置,另一个存储了加热器的位置,要求输出加热器的最小半径,使得加热器可以覆盖所有房子。房屋和加热器都是一维水平向量。

2、假设房屋位置和加热器位置如下:(三角形代表房子,圆形代表加热器)

△△△△△△△△△△△△

    ○             ○         ○

那么我们最直接的想法就是找到房子两边的上下两个加热器,比如第3个房子就找第1和第2个加热器,第8个房子就找第2和第3个加热器,然后看这两个加热器哪个距离它更近。

把最小距离存储起来,里面最大的那个数值就是我们要的最小半径。

那么如何找到房子两边的上下两个加热器呢?用二分查找,好像有点慢。

我们可以这样做:

第一次对房子和加热器做循环,从左边开始,找到大于等于房子位置的加热器,加热器位置减去房子位置,得到距离,这是上加热器跟房子的距离。

第二次对房子和加热器做循环,从右边开始,找到小于房子位置的加热器,房子位置减去加热器位置,得到距离,这是下加热器跟房子的距离。

经过两次循环,一次上限减房子位置,一次房子位置减下限,我们就可以直接得到距离。

代码如下:

    int findRadius(vector<int>& houses, vector<int>& heaters) 
    {
        sort(houses.begin(),houses.end());//排序
        sort(heaters.begin(),heaters.end());
        int s1=houses.size(),s2=heaters.size(),max1=0;//max1用在最后,存储最大数值
        vector<int> res(s1,INT_MAX);//初始值为INT_MAX
        for(int i=0,h=0;i<s1&&h<s2;)//上限-房子位置
        {
            if(heaters[h]>=houses[i])
            {
                res[i]=heaters[h]-houses[i];
                i++;
            }  
            else
                h++;
        }
        for(int i=s1-1,h=s2-1;i>=0&&h>=0;)//房子位置-下限,跟原本数值比较,存储小的值
        {
            if(heaters[h]<houses[i])
            {
                res[i]=min(houses[i]-heaters[h],res[i]);
                i--;
            }
            else
                h--;
        }
        for(int i=0;i<s1;i++)
        {
            if(res[i]>max1)
                max1=res[i];
        }
        return max1;
    }

上述代码实测73ms,beats 90.81% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-455-Assign Cookies

    chenjx85
  • leetcode-461-Hamming Distance

    chenjx85
  • leetcode-189-Rotate Array

    Given an array, rotate the array to the right by k steps, where k is non-negativ...

    chenjx85
  • JAVA类Integer

    今天带来的是Integer,想必大家都不会陌生,下面会大家从属性、内部类、好玩的几个方法入手,来简单解析下Integer这个类。

    用户6055494
  • 【Java面试题系列】:Java基础知识面试题,看这一篇就够了

    参加过社招的同学都了解,进入一家公司面试开发岗位时,填写完个人信息后,一般都会让先做一份笔试题,然后公司会根据笔试题的回答结果,确定要不要继续此次面试,如果答的...

    用户5546570
  • 腾讯智造,新一代云数据库CynosDB,“C”位出道!

    CynosDB是腾讯云自研的新一代高性能高可用的企业级分布式云数据库。融合了传统数据库、云计算与新硬件的优势,100%兼容开源数据库,百万级QPS的高吞吐,不限...

    腾讯云数据库 TencentDB
  • 780. Reaching Points

    stack over flow,原因很简单,如例子[5, 7, 455955547, 420098884],想想它的递归深度。

    用户1147447
  • Memcached基础了解

    老七Linux
  • 每日一题 剑指offer(替换空格)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 不知道CynosDB为什么叫真正的云原生数据库?腾讯云数据库的产品欧巴今天跟你聊一聊

    注:本文摘自2018年11月22日腾讯云数据库CynosDB新品发布会的演讲实录。随着互联网信息的发展,大家也对云这个词汇也不是特别陌生了,作为全球首选的云服务...

    腾讯云数据库 TencentDB

扫码关注云+社区

领取腾讯云代金券