Leetcode 1274:矩形内船只的数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1274:矩形内船只的数目(超详细的解法!!!)

in leetcode with 0 comment

(此题是 *交互式问题* )

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

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

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

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

示例:

输入:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
输出:3
解释:在 [0,0] 到 [4,4] 的范围内总共有 3 艘船。

提示:

解题思路

由于查询次数有限,所以很容易想到分治的思路去考虑。将矩形分成相同大小的四个部分,然后在这四个部分中分别查找。

class Solution(object):
    def countShips(self, sea: 'Sea', tp: 'Point', lp: 'Point') -> int:
        if lp.x > tp.x or lp.y > tp.y or not sea.hasShips(tp, lp):
            return 0
        if tp.x == lp.x and tp.y == lp.y:
            return 1
        nx, ny = (tp.x + lp.x)//2, (tp.y + lp.y)//2
        return self.countShips(sea, Point(nx, tp.y), Point(lp.x, ny + 1)) +\
            self.countShips(sea, Point(nx, ny), lp) + \
            self.countShips(sea, tp, Point(nx + 1, ny + 1)) + \
            self.countShips(sea, Point(tp.x, ny), Point(nx + 1, lp.y))

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses