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