LC: 1274. Number of Ships in a Rectangle
1274. Number of Ships in a Rectangle
(This problem is an interactive problem.)
Each ship is located at an integer point on the sea represented by a cartesian plane, and each integer point may contain at most 1 ship.
You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true If there is at least one ship in the rectangle represented by the two points, including on the boundary.
Given two points: the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.
Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Example :
Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.Example 2:
Input: ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]
Output: 3Constraints:
On the input
shipsis only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the givenhasShipsAPI, without knowing theshipsposition.0 <= bottomLeft[0] <= topRight[0] <= 10000 <= bottomLeft[1] <= topRight[1] <= 1000topRight != bottomLeft
The Essence:
Obwohl die Anzahl der Schiffe in dem größten Rechteck gesucht wird, haben wir keine direkte Method dafür. Die uns gegebene Methode Sea.hasShips() funktioniert jedoch für jeden Rechteck, d.h. wir können den großen Rechteck in kleinere Rechtecke teilen. Wenn wir mit diesem Verfahren weitermachen, begegnet uns Rechtecke mit der Fläche 1, wofür die Methode hasShips nur 1 oder 0 zurückgeben kann.
1274. Number of Ships in a Rectangle:
Details:
Man kann den Rechteck einfach in 4 Teilen rekursiv untersuchen und dann die Ergebnisse für kleinere Rechtecke summieren.
Default Code:
Last updated