题目大意：
矩阵内船只的数量
(此题是 交互式问题)
在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。
有一个函数 Sea.hasShips(topRight, bottomLeft)，输入参数为右上角和左下角两个点的坐标，当且仅当这两个点所表示的矩形区域（包含边界）内至少有一艘船时，这个函数才返回 true，否则返回 false。
给你矩形的右上角 topRight 和左下角 bottomLeft 的坐标，请你返回此矩形内船只的数目。题目保证矩形内 至多只有 10 艘船。
调用函数 hasShips 超过 400 次 的提交将被判为 错误答案（Wrong Answer）。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。
示例1：
输入： ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0] 输出：3 解释：在 [0,0] 到 [4,4] 的范围内总共有 3 艘船。
提示：
- ships 数组只用于评测系统内部初始化。你无法得知 ships 的信息，所以只能通过调用 hasShips 接口来求解。
- 0 <= bottomLeft[0] <= topRight[0] <= 1000
- 0 <= bottomLeft[1] <= topRight[1] <= 1000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1274
解题思路分析：
本题如果采用暴力解，需要查看每一个点上是否有船只，这样最多需要查询1000乘以1000次，肯定超过题目要求的最多查询次数。因此我们可以考虑采用二分查找的思路，由于是2位数组，因此二分需要将当前区域分成四个部分，以中心点为二分中心，分成左上，左下，右上和右下4部分，分别查看四个区域内是否有船只，如果没有，该区域内则不需要再次划分。反之如果存在船只，这需要继续二分，直到将区域分成1个点为止。不断二分的过程实际上是递归操作。每一层递归返回当前区域内船只的总数量，而当前区域内的总数量是4个部分船只数量的和。
实现代码：
public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
// 如果当前区域为一个点，那么当前区域如果有船只，返回1，反之返回0
if(topRight[0]==bottomLeft[0] && topRight[1]==bottomLeft[1]){
return sea.hasShips(topRight, bottomLeft)?1:0;
}
// 如果当前区间不合理，返回0
if(bottomLeft[0]>topRight[0] || bottomLeft[1]>topRight[1]){
return 0;
}
// 当前区域中心横坐标
int midX=(topRight[0]+bottomLeft[0])/2;
// 当前区域中心纵坐标
int midY=(topRight[1]+bottomLeft[1])/2;
int res=0; // 返回结果
// 如果左上区域存在船只，递归继续二分
if(sea.hasShips(new int[]{midX,topRight[1]},new int[]{bottomLeft[0],midY+1})){
res+=countShips(sea, new int[]{midX, topRight[1]},
new int[]{bottomLeft[0],midY+1});
}
// 如果右上区域存在船只，递归继续二分
if(sea.hasShips(topRight, new int[]{midX+1,midY+1})){
res+=countShips(sea, topRight, new int[]{midX+1,midY+1});
}
// 如果右上区域存在船只，递归继续二分
if(sea.hasShips(new int[]{midX,midY}, bottomLeft)){
res+=countShips(sea, new int[]{midX,midY}, bottomLeft);
}
// 如果右下区域存在船只，递归继续二分
if(sea.hasShips(new int[]{topRight[0],midY},new int[]{midX+1,bottomLeft[1]})){
res+=countShips(sea, new int[]{topRight[0],midY},
new int[]{midX+1,bottomLeft[1]});
}
return res;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 65.08% of Java online submissions for Number of Ships in a Rectangle.
Memory Usage: 27.6 MB, less than 100.00% of Java online submissions for Number of Ships in a Rectangle.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1274-number-of-ships-in-a-rectangle-解题思路分析/