Day3 475. 供暖器 - 力扣（LeetCode） (leetcode-cn.com)

本题没搞懂

题目

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

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

示例 1:

  1. 输入: houses = [1,2,3], heaters = [2]
  2. 输出: 1
  3. 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

  1. 输入: houses = [1,2,3,4], heaters = [1,4]
  2. 输出: 1
  3. 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

示例 3：

  1. 输入：houses = [1,5], heaters = [2]
  2. 输出：3

提示：

  • 1 <= houses.length, heaters.length <= 3 * 104
  • 1 <= houses[i], heaters[i] <= 109

    贴几个答案

    carbon.png ```python class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -> int:
    1.   heaters = heaters + [-inf, inf]
    2.   houses.sort()
    3.   heaters.sort()
    4.   i, j, ans = 0, 0, 0
    5.   while i < len(houses):
    6.       cur = inf
    7.       while heaters[j] <= houses[i]:
    8.           cur = houses[i] - heaters[j]
    9.           j += 1
    10.       cur = min(cur, heaters[j] - houses[i])
    11.       ans = max(cur, ans)
    12.       i += 1
    13.       j -= 1
    14.   return ans
![carbon2.png](https://cdn.nlark.com/yuque/0/2021/png/23221561/1640009279055-38a2333f-3af7-4130-bf58-783499db6260.png#clientId=ud2298a78-3b37-4&from=drop&id=u2096f48c&margin=%5Bobject%20Object%5D&name=carbon2.png&originHeight=2544&originWidth=3672&originalType=binary&ratio=1&size=563963&status=done&style=none&taskId=ua3df0877-c73a-4932-91fe-c50515a6602)
```python
class Solution:

    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        houses.sort()
        heaters.append(float("-inf"))
        heaters.append(float("inf"))
        heaters.sort()
        n1, n2 = len(houses), len(heaters)

        ans = 0
        i, j = 0, 1
        while i < n1 and j < n2:
            if houses[i] == heaters[j]:
                i += 1
                j += 1
            elif houses[i] < heaters[j]:
                ans = max(ans, min(heaters[j] - houses[i], houses[i] - heaters[j-1]))
                i += 1
            else:
                j += 1

        return ans

我看不懂这些大佬解法,我只会暴力解法

只不过超时了….(

…..我的一个案例运行6000ms, 大佬30个案例运行84ms…..
carbon3.png

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        single_list = []
        for i in houses:
            temp = []
            for n in heaters:
                ans = abs(i - n)
                temp.append(ans)
            single_list.append(min(temp))
        return max(single_list)

笔记

  1. inf表示的是 无穷 大 / 小
  2. 其他的代码看不懂,以后再说.