LeetCode 题解

LeetCode 第 5136 题：矩形内船只的数目（困难）

(此题是 交互式问题 )

在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。

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

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

调用函数 hasShips 超过400次 的提交将被判为 错误答案（Wrong Answer） 。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。

示例：

img

输入：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ships-in-a-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java 代码：

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 */

interface Sea {
    boolean hasShips(int[] topRight, int[] bottomLeft);
}

public class Solution {

    /**
     * 根据提示 1 使用分治法
     *
     * @param sea
     * @param topRight   右上角的点
     * @param bottomLeft 左下角的点
     * @return
     */
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        int res = 0;

        // 左下角的点从水平上看靠左边
        // 右上角的点从水平上看靠右边
        // 用 X 表示横坐标，用 Y 表示纵坐标

        // 左下角的横坐标、纵坐标
        int leftX = bottomLeft[0];
        int leftY = bottomLeft[1];

        // 右上角的横坐标、纵坐标
        int rightX = topRight[0];
        int rightY = topRight[1];

        // 如果都挤到一个点了
        if (leftX == rightX && leftY == rightY
                && sea.hasShips(new int[]{rightX, rightY}, new int[]{leftX, leftY})) {
            return 1;
        }

        int midX = (leftX + rightX) >>> 1;
        int midY = (leftY + rightY) >>> 1;

        // 要保证不重不漏

        // 左上角
        if (leftX <= midX && midY + 1 <= rightY && sea.hasShips(new int[]{midX, rightY}, new int[]{leftX, midY + 1})) {
            res += countShips(sea, new int[]{midX, rightY}, new int[]{leftX, midY + 1});
        }

        // 右上角
        if (midX + 1 <= rightX && midY + 1 <= rightY && sea.hasShips(new int[]{rightX, rightY}, new int[]{midX + 1, midY + 1})) {
            res += countShips(sea, new int[]{rightX, rightY}, new int[]{midX + 1, midY + 1});
        }

        // 左下角
        if (leftX <= midX && leftY <= midY && sea.hasShips(new int[]{midX, midY}, new int[]{leftX, leftY})) {
            res += countShips(sea, new int[]{midX, midY}, new int[]{leftX, leftY});
        }

        // 右下角
        if (midX + 1 <= rightX && leftY <= midY && sea.hasShips(new int[]{rightX, midY}, new int[]{midX + 1, leftY})) {
            res += countShips(sea, new int[]{rightX, midY}, new int[]{midX + 1, leftY});
        }
        return res;
    }
}

（本节完）

←