LeetCode algorithm learning – binary search – heater

Hi, everybody. Today, I’m going to share with you the next LeetCode medium difficulty problem [heaters].

Here is mainly to share ideas and comments, for everyone to better understand the problem solution, the code part is converted into javascript code by referring to LeetCode,

The title

Winter has set in. Your task is to design a radiator with a fixed heating radius to heat all the houses.

Every house within the heating radius of the heater can be heated.

Now, give the location of the houses and heaters to be heaters in a horizontal line. Please find and return the minimum heating radius to cover all the houses.

Note: All heaters follow your radius standard, as does the heating radius.

Example 1: Input: Houses = [1,2,3], Heaters = [2] Output: 1 Explanation: There is only one heater in position 2. If we set the heating radius to 1, then all the houses will be heated. Example 2: Input: Houses = [1,2,3,4], Output: 1 Explanation: There are two heaters on position 1 and position 4. We need to set the heating radius to 1 so that all the houses can be heated. Example 3: input: houses = [1,5], heaters = [2] output: 3 source: LeetCode link: https://leetcode-cn.com/problems/heaters copyright is owned by collateral.com. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Analysis of the

1. Assume that the radius is R, and the coverage area of each heater is [Vox-R, vox-R + R]

2. All heaters must cover all houses

solution

1. The dichotomy

2. The iteration method

Solution a:dichotomy

Train of thought1.To comply with the conditions of binary search, make houses and Heaters into ascending order2.The interval of nearest radius radius is [0, Max (houses [houses. Length -1],heater[heaters.length-1]) 】3.Iteratively buy a heaters and figure out its coverage area. If all the houses are covered in the end, it means to find the answer.4.Find the minimum */ using the find lvalue in binary searchvar findRadius = function (houses, heaters) {
  Houses and Heasters are changed to ascending order to qualify for binary search
  houses.sort((a, b) = > a - b);
  heaters.sort((a, b) = > a - b);

  // Find the radius interval
  let left = 0;
  let right = Math.max(heaters[heaters.length - 1], houses[houses.length - 1]);

  // Find the smallest RADIUS using the leftmost extremum method in binary search
  while (left <= right) {
    // Mid equals radius
    const radius = Math.floor(left + (right - left) / 2);
    if (pass(radius)) {
      right = radius - 1;
    } else {
      left = radius + 1; }}return left;

  function pass(radius) {
    let last_next_house_index = 0;
    for (const heater of heaters) {
      // Find the position of the leftmost house covered
      const left_house_index = bisect_left(houses, heater - radius);
      // If the position is greater than the index of the next house on the right-most side of the previous round, then there is no full coverage
      if (left_house_index > last_next_house_index) {
        return false;
      }
      // Find the index of the next house covered by the right-most house (bisect_right)
      const next_house_index = bisect_right(houses, heater + radius);
      // Record the rightmost position
      last_next_house_index = next_house_index;
      // If the index of the right-most position is greater than the length of houses, it indicates full coverage
      if (next_house_index >= houses.length) {
        return true; }}If it is heaters all round but not complete, RADIUS is also unqualified
    return false;
  }

  function bisect_left(nums, target) {
    let l = 0;
    let r = nums.length - 1;

    while (l <= r) {
      const mid = Math.floor(l + (r - l) / 2);
      if (nums[mid] >= target) {
        r = mid - 1;
      } else {
        l = mid + 1; }}return l;
  }

  function bisect_right(nums, target) {
    let l = 0;
    let r = nums.length - 1;

    while (l <= r) {
      const mid = Math.floor(l + (r - l) / 2);
      if (nums[mid] <= target) {
        l = mid + 1;
      } else {
        r = mid - 1; }}returnl; }};/* Complexity time O(logN*logK) N is the number of RADIUS interval arrays, and k is the number of houses O(1) */
Copy the code

Method 2:Iterative method

Code reference leetcode-cn.com/problems/he…

thinking1.Go through house once, and obtain the distance DIS of each house corresponding to the nearest heater in turn2.Get the maximum dis */var findRadius = function (houses, heaters) {
  houses.sort((a, b) = > a - b);
  heaters.sort((a, b) = > a - b);
  let res = 0;
  let i = 0;
  for (const house of houses) {
    // Absolute distance between the current Heater and house
    let currentHeaterDis = Math.abs(heaters[i] - house);
    // The absolute distance between the next heater and house
    let nextHeaterDis = Math.abs(heaters[i + 1] - house);
    // If the current heater is larger than the next one, we need to take the next heater to compare the distance
    while (i < heaters.length - 1 && currentHeaterDis >= nextHeaterDis) {
      i++;
      // recalculate the distance
      currentHeaterDis = Math.abs(heaters[i] - house);
      nextHeaterDis = Math.abs(heaters[i + 1] - house);
    }

    res = Math.max(res, currentHeaterDis);
  }

  return res;
};

/* Complexity time O(n) n is the number space of house O(1) */
Copy the code

conclusion

This problem is to see if the problem can be converted into an ordered array, so that the application of dichotomy or iteration can be applied

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]