526互联

[LeetCode] 1274. Number of Ships in a Rectangle

发布时间 2023-10-31 03:56:00作者: CNoodle

(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: 3

Constraints:
On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000
topRight != bottomLeft

矩阵内船只的数量。

(此题是 交互式问题 ) 在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。

有一个函数 Sea.hasShips(topRight, bottomLeft) ，输入参数为右上角和左下角两个点的坐标，当且仅当这两个点所表示的矩形区域（包含边界）内至少有一艘船时，这个函数才返回 true ，否则返回 false 。

给你矩形的右上角 topRight 和左下角 bottomLeft 的坐标，请你返回此矩形内船只的数目。题目保证矩形内至多只有 10 艘船。

调用函数 hasShips 超过400次 的提交将被判为 错误答案（Wrong Answer） 。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。
————————————————
版权声明：本文为CSDN博主「信仰..」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/haut_ykc/article/details/103355227

思路是分治。因为题目说了坐标系的长宽各不超过 1000，船的坐标都在每一个整数点上，那么极端情况下坐标系内的整数点的个数 = 1000 * 1000 = 1,000,000 = 10^6。如果用暴力解是不可能都找的到的因为题目规定调用函数 hasShips 不能超过 400 次。由此我们想到分治的做法。但是分治也有一个问题，比如将 input 坐标系等分成4个更小的正方形，按照这样的分法，因为如果原坐标系内每个整数点的位置都有一艘船的话，极限情况还是需要遍历到每个点。好在题目又说了保证矩形内至多只有 10 艘船，所以分治的时候我们是可以去掉那些没有船的矩形的。

思路是用分治的做法每次将矩形分成四等分，然后在这些更小的矩形中去调用 hasShips 函数。这道题感觉还有一个考点就是要说清楚时间空间复杂度。因为分治是分成四等分，相当于是一个四叉树，那么最多需要分治几次/树的深度是多少呢？log4(1,000,000) = 9.97 约等于 10，所以递归深度最多是 10，应该不会 stack overflow。

image

https://leetcode.com/problems/number-of-ships-in-a-rectangle/Figures/1274/Ships_SubRectangles.png

时间 - ?
空间 - ?
Java实现

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *     public boolean hasShips(int[] topRight, int[] bottomLeft);
 * }
 */

class Solution {
	public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
		// If the current rectangle does not contain any ships, return 0.         
		if (bottomLeft[0] > topRight[0] || bottomLeft[1] > topRight[1]) {
			return 0;
		}
		if (!sea.hasShips(topRight, bottomLeft)) {
			return 0;
		}

		// If the rectangle represents a single point, a ship is located
		if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) {
			return 1;
		}

		// Recursively check each of the 4 sub-rectangles for ships
		int midX = (topRight[0] + bottomLeft[0]) / 2;
		int midY = (topRight[1] + bottomLeft[1]) / 2;
		return countShips(sea, new int[] { midX, midY }, bottomLeft) +
				countShips(sea, topRight, new int[] { midX + 1, midY + 1 }) +
				countShips(sea, new int[] { midX, topRight[1] }, new int[] { bottomLeft[0], midY + 1 }) +
				countShips(sea, new int[] { topRight[0], midY }, new int[] { midX + 1, bottomLeft[1] });
	}
}