口碑好的做pc端网站,中国建筑人事部大全,wordpress ajax登陆,网站tkd怎么做文章目录1. 题目2. 解题1. 题目
(此题是 交互式问题 )
在用笛卡尔坐标系表示的二维海平面上#xff0c;有一些船。
每一艘船都在一个整数点上#xff0c;且每一个整数点最多只有 1 艘船。
有一个函数 Sea.hasShips(topRight, bottomLeft) #xff0c;输入参数为右上角和…
文章目录1. 题目2. 解题1. 题目
(此题是 交互式问题 )
在用笛卡尔坐标系表示的二维海平面上有一些船。
每一艘船都在一个整数点上且每一个整数点最多只有 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 艘船。提示
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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
计算横纵坐标的中点将矩形分成4块。
/*** // This is Seas API interface.* // You should not implement it, or speculate about its implementation* class Sea {* public:* bool hasShips(vectorint topRight, vectorint bottomLeft);* };*/class Solution { //Cint sum 0;
public:int countShips(Sea sea, vectorint topRight, vectorint bottomLeft) {if(topRight[0] bottomLeft[0] || topRight[1] bottomLeft[1]|| !sea.hasShips(topRight, bottomLeft))return 0;if(topRight bottomLeft)return sum;int xmid (topRight[0] bottomLeft[0])/2;int ymid (topRight[1] bottomLeft[1])/2;countShips(sea, {xmid, ymid}, bottomLeft);countShips(sea, {topRight[0], ymid}, {xmid1, bottomLeft[1]});countShips(sea, {xmid, topRight[1]}, {bottomLeft[0], ymid1});countShips(sea, topRight, {xmid1, ymid1});return sum;}
};#
# This is Seas API interface.
# You should not implement it, or speculate about its implementation
#
#class Sea(object):
# def hasShips(self, topRight: Point, bottomLeft: Point) - bool:
#
#class Point(object):
# def __init__(self, x: int, y: int):
# self.x x
# self.y yclass Solution(object): #py3def __init__(self):self.sum 0def countShips(self, sea: Sea, topRight: Point, bottomLeft: Point) - int:if topRight.x bottomLeft.x or topRight.y bottomLeft.y or not sea.hasShips(topRight, bottomLeft):return 0xmid (topRight.x bottomLeft.x)//2ymid (topRight.y bottomLeft.y)//2if topRight.x bottomLeft.x and topRight.y bottomLeft.y:self.sum 1return self.sumself.countShips(sea, Point(xmid, ymid), bottomLeft)self.countShips(sea, Point(topRight.x, ymid), Point(xmid1, bottomLeft.y))self.countShips(sea, Point(xmid, topRight.y), Point(bottomLeft.x, ymid1))self.countShips(sea, topRight, Point(xmid1, ymid1))return self.sum我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
