← Static tasks

1274. Number of Ships in a Rectangle

leetcode hard

#csharp#hard#leetcode#recursion#two-pointers

Task

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input:

ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]

Output: 3

C# solution

matched/original
public class Solution {
    public int CountShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.HasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return CountShips(sea, new Point(midX, midY), bottomLeft) +
               CountShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               CountShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               CountShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.HasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return CountShips(sea, new Point(midX, midY), bottomLeft) +
               CountShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               CountShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               CountShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}

Java solution

matched/original
public class Solution {
    public int countShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return countShips(sea, new Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               countShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               countShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}

JavaScript solution

matched/original
var countShips = function(sea, topRight, bottomLeft) {
    if (!sea.hasShips(topRight, bottomLeft)) {
        return 0;
    }
    if (topRight.x === bottomLeft.x && topRight.y === bottomLeft.y) {
        return 1;
    }
    const midX = Math.floor((topRight.x + bottomLeft.x) / 2);
    const midY = Math.floor((topRight.y + bottomLeft.y) / 2);
    return countShips(sea, {x: midX, y: midY}, bottomLeft) +
           countShips(sea, topRight, {x: midX + 1, y: midY + 1}) +
           countShips(sea, {x: midX, y: topRight.y}, {x: bottomLeft.x, y: midY + 1}) +
           countShips(sea, {x: topRight.x, y: midY}, {x: midX + 1, y: bottomLeft.y});
};

Go solution

matched/original
func countShips(sea Sea, topRight, bottomLeft Point) int {
    if !sea.HasShips(topRight, bottomLeft) {
        return 0
    }
    if topRight.x == bottomLeft.x && topRight.y == bottomLeft.y {
        return 1
    }
    midX := (topRight.x + bottomLeft.x) / 2
    midY := (topRight.y + bottomLeft.y) / 2
    return countShips(sea, Point{midX, midY}, bottomLeft) +
           countShips(sea, topRight, Point{midX + 1, midY + 1}) +
           countShips(sea, Point{midX, topRight.y}, Point{bottomLeft.x, midY + 1}) +
           countShips(sea, Point{topRight.x, midY}, Point{midX + 1, bottomLeft.y})
}

Explanation

Algorithm

Разделите текущий прямоугольник на четыре меньших прямоугольника

Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

Суммируйте количество кораблей в подпрямоугольниках для получения общего количества кораблей в текущем прямоугольнике.

😎