矩形内船只的数目

1274. 矩形内船只的数目

(此题是 交互式问题 )

在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 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 艘船。

示例 2:

输入：ans = [[1,1],[2,2],[3,3]], topRight = [1000,1000], bottomLeft = [0,0]
输出：3

提示：

ships 数组只用于评测系统内部初始化。你必须“蒙着眼睛”解决这个问题。你无法得知 ships 的信息，所以只能通过调用 hasShips 接口来求解。
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000
topRight != bottomLeft

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * // This is Sea's API interface. * // You should not implement it, or speculate about its implementation * class Sea { * public: * bool hasShips(vector<int> topRight, vector<int> bottomLeft); * }; */ class Solution { public: int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-21 23:29:07

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * type Sea struct {
 *     func hasShips(topRight, bottomLeft []int) bool {}
 * }
 */
func countShips(sea Sea, tr, bl []int) int {
	if tr[0] < bl[0] || tr[1] < bl[1] || !sea.hasShips(tr, bl) {
		return 0
	}

	if tr[0] == bl[0] && tr[1]==bl[1] {
		return 1
	}

	hx, hy, lx, ly := tr[0], tr[1], bl[0], bl[1]
	mx, my := (hx+lx)>>1, (hy+ly)>>1
	return countShips(sea, tr, []int{mx + 1, my + 1}) + countShips(sea, []int{mx, my}, bl) + countShips(sea, []int{mx, hy}, []int{lx, my + 1}) + countShips(sea, []int{hx, my}, []int{mx + 1, ly})
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-21 23:28:25

# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Sea:
#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
#
#class Point:
#	def __init__(self, x: int, y: int):
#		self.x = x
#		self.y = y

class Solution:
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        # 如果当前矩形不包含船，则返回 0。           
        if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):
            return 0
        if not sea.hasShips(topRight, bottomLeft):
            return 0

        # 如果矩形代表一个点，则定位了一艘船
        if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y):
            return 1

        # 递归地检查 4 个子矩形中的船
        mid_x = (topRight.x + bottomLeft.x) // 2
        mid_y = (topRight.y + bottomLeft.y) // 2
        return self.countShips(sea, Point(mid_x, mid_y), bottomLeft) + \
               self.countShips(sea, topRight, Point(mid_x + 1, mid_y + 1)) + \
               self.countShips(sea, Point(mid_x, topRight.y), Point(bottomLeft.x, mid_y + 1)) + \
               self.countShips(sea, Point(topRight.x, mid_y), Point(mid_x + 1, bottomLeft.y))
               
class Solution2:
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point', claim: bool=False) -> int:
        x1, y1 = topRight.x, topRight.y
        x2, y2 = bottomLeft.x, bottomLeft.y

        if x1 < x2 or y1 < y2:
            return 0

        judge = True if claim else sea.hasShips(topRight, bottomLeft)
        if not judge:
            return 0
        if (x1, y1) == (x2, y2):
            return 1

        if x1 == x2:
            ymid = (y1 + y2) // 2
            A = self.countShips(sea, Point(x1, ymid), Point(x1, y2))
            return A + self.countShips(sea, Point(x1, y1), Point(x1, ymid + 1), A == 0)
        else:
            xmid = (x1 + x2) // 2
            A = self.countShips(sea, Point(xmid, y1), Point(x2, y2))
            return A + self.countShips(sea, Point(x1, y1), Point(xmid + 1, y2), A == 0)

java 解法, 执行用时: 0 ms, 内存消耗: 39.3 MB, 提交时间: 2023-10-21 23:27:52

/**
 * // 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) {
        // 如果当前矩形不包含船，则返回 0。         
        if (bottomLeft[0] > topRight[0] || bottomLeft[1] > topRight[1])
            return 0;
        if (!sea.hasShips(topRight, bottomLeft))
            return 0;

        // 如果矩形代表一个点，则定位了一艘船
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
            return 1;

        // 递归地检查 4 个子矩形中的船
        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]});
    }
}

cpp 解法, 执行用时: 32 ms, 内存消耗: 27.7 MB, 提交时间: 2023-10-21 23:27:31

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

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        // 如果当前矩形不包含船，则返回 0。       
        if (bottomLeft[0] > topRight[0] || bottomLeft[1] > topRight[1])
            return 0;
        if (!sea.hasShips(topRight, bottomLeft))
            return 0;

        // 如果矩形代表一个点，则定位了一艘船
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
            return 1;

        // 递归地检查 4 个子矩形中的船
        int midX = (topRight[0] + bottomLeft[0]) / 2;
        int midY = (topRight[1] + bottomLeft[1]) / 2;
        return countShips(sea, {midX, midY}, bottomLeft) +
               countShips(sea, topRight, {midX + 1, midY + 1}) +
               countShips(sea, {midX, topRight[1]}, {bottomLeft[0], midY + 1}) +
               countShips(sea, {topRight[0], midY}, {midX + 1, bottomLeft[1]});
    }

    int countShips2(Sea& sea, vector<int> topRight, vector<int> bottomLeft, bool claim = false) {
        int x1 = topRight[0], y1 = topRight[1];
        int x2 = bottomLeft[0], y2 = bottomLeft[1];

        if (x1 < x2 || y1 < y2) {
            return 0;
        }

        bool judge = (claim ? true : sea.hasShips(topRight, bottomLeft));
        if (!judge) {
            return 0;
        }
        if (x1 == x2 && y1 == y2) {
            return 1;
        }

        if (x1 == x2) {
            int ymid = (y1 + y2) / 2;
            int A = countShips2(sea, {x1, ymid}, {x1, y2});
            return A + countShips2(sea, {x1, y1}, {x1, ymid + 1}, A == 0);
        }
        else {
            int xmid = (x1 + x2) / 2;
            int A = countShips2(sea, {xmid, y1}, {x2, y2});
            return A + countShips2(sea, {x1, y1}, {xmid + 1, y2}, A == 0);
        }
    }
};

上一题

下一题

详情