java leetcode之[中等]475. 供暖器

题目的链接在这里:


题目大意

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。

说明:所有供暖器都遵循你的半径标准,加热的半径也一样。


一、示意图

二、解题思路

暴力判断(出错了)

暴力判断(出错了)

代码如下:

class Solution {
          
   
 public int findRadius(int[] houses, int[] heaters) {
          
   
        //houses是一条水平线上的房间 数值表示的是 有房间的位置
        //heaters就是 供暖器 现在要确定他的半径 但供暖器可能存在很多个
        //所以应该是  heaters的最左边的值 减去半径要最起码小于等于起点 然后最右边的值 加上半径 最起码要大于等于重点
        //并且 无论怎么说 需要 heaters之间能够相连 那就直接暴力判断
        //这个没必要了
       // int len=houses[houses.length-1]-houses[0];
        //len是最长可能存在的长度
        int res=1;
        boolean flag=true;
        //然后开始遍历
        for(int i=0;i<=100000;i++){
          
   
            //还有一种情况是 供暖期就在houses位置上
            res=i;
            if((heaters[0]-i)<=houses[0]&&heaters[heaters.length-1]+i>=houses[houses.length-1]){
          
   
                //这个就是 起点要包括到 终点要包括到
                //然后就变成了 需要判断 供热器之间 能不能把所有的houses都包含到
                for(int j=0;j<heaters.length-1;j++){
          
   
                    //应该是这样对比的 左边的右半径+i 大于等于 (右边的左半径-i) 才叫不符合条件
                    if((heaters[j]+i+1)<(heaters[j+1]-i)){
          
   
                        //说明前一个的映射范围没有包含
                        //应该需要这样判断 他错了就直接break
                        flag=false;
                        break;
                    }
                }
                //如果到最后都没有变的话  说明这个点就是可以的
                //应该是在这判断的
                if(flag){
          
   
                    return res;
                }
            }
            //所以这里还需要再初始化一下
            flag=true;
        }
        return res;
    }
}
经验分享 程序员 微信小程序 职场和发展