难度: Hard
Submission
运行时间: 32 ms
内存: 16.1 MB
# """
# 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', claim = False) -> int:
# if (bottomLeft.x > topRight.x) or (bottomLeft.y > topRight.y):
# return 0
# if not hasShips(topRight, bottomLeft):
# return 0
# if (topRight.x == bottomLeft.x) and (topRight.y == bottomLeft.y) and hasShips(topRight, bottomLeft):
# return 1
# mid_x = (topRight.x + bottomLeft.x) // 2
# mid_y = (topRight.y + bottomLeft.y) // 2
# 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)
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 == x2 and y1 == y2 :
return 1
if x1 == x2:
y_mid = (y1 + y2) //2
A = self.countShips(sea, Point(x1, y_mid), Point(x1, y2))
return A + self.countShips(sea, Point(x1, y1), Point(x1, y_mid + 1), A == 0)
else:
x_mid = (x1 + x2) //2
A = self.countShips(sea, Point(x_mid, y1), Point(x2, y2))
return A + self.countShips(sea, Point(x1, y1), Point(x_mid + 1, y2), A == 0)
Explain
此题解的思路基于二分搜索和递归的方法来确定矩形区域内是否包含船只。首先，如果 topRight 的坐标小于或等于 bottomLeft 的坐标，或者通过调用 API hasShips 发现当前矩形区域内没有船只，则直接返回 0。如果矩形区域缩小到一个点，即 topRight 和 bottomLeft 坐标相同，且该点有船只，则返回 1。否则，根据 x 轴或 y 轴的坐标是否相等来决定如何进一步划分区域。如果 x 坐标相同，则沿 y 轴划分；如果 y 坐标相同，则沿 x 轴划分。对每个子区域递归地调用 countShips 函数，并将结果相加得到总船只数。
时间复杂度: O(logN * logM)
空间复杂度: O(logN + logM)
# Solution class for counting ships in a rectangular sea region
class Solution:
def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point', claim=False) -> int:
x1, y1 = topRight.x, topRight.y
x2, y2 = bottomLeft.x, bottomLeft.y
if x1 < x2 or y1 < y2:
return 0 # No valid rectangle
judge = True if claim else sea.hasShips(topRight, bottomLeft)
if not judge:
return 0 # No ships in this region
if x1 == x2 and y1 == y2:
return 1 # Single point with a ship
if x1 == x2:
y_mid = (y1 + y2) // 2
A = self.countShips(sea, Point(x1, y_mid), Point(x1, y2)) # Left half
return A + self.countShips(sea, Point(x1, y1), Point(x1, y_mid + 1), A == 0) # Right half
else:
x_mid = (x1 + x2) // 2
A = self.countShips(sea, Point(x_mid, y1), Point(x2, y2)) # Lower half
return A + self.countShips(sea, Point(x1, y1), Point(x_mid + 1, y2), A == 0) # Upper half
Explore
在递归函数中，参数`claim`主要用于优化API调用，避免重复检测某些区域内是否有船。当`claim`为True时，表示调用者已确定该区域有船，因此不需要再次调用`hasShips`方法进行检测。这样可以减少API的调用次数，提高算法的效率。在逻辑上，如果上一次递归返回的结果是有船的（例如A不等于0），则下一次递归时将`claim`设置为True，直接认为该区域有船。
如果`topRight`的x坐标小于`bottomLeft`的x坐标，或者`topRight`的y坐标小于`bottomLeft`的y坐标，这表明定义的矩形区域是不合理的。例如，矩形的上边界应该在下边界的上方，右边界应该在左边界的右侧。如果坐标设置错误，将导致区域无效，因此直接返回0，表示该区域内没有船只。
是的，这种情况已被考虑。如果`topRight`和`bottomLeft`坐标相同，即代表区域缩小到一个单点，此时会通过`hasShips`方法检查这个点是否有船。如果该点有船，则返回1；如果没有船，则`hasShips`方法会返回False，递归也随之返回0，表示这个点没有船只。
决定沿x轴还是y轴划分主要根据当前考虑的矩形的长和宽。通常选择将较长的维度进行划分，这样可以更均匀地分割区域，有助于更平衡的递归深度和可能更快地缩小搜索范围。如果x坐标相同（即矩形在x方向上的长度为0），则沿y轴划分；如果y坐标相同（即矩形在y方向上的长度为0），则沿x轴划分。如果两个坐标都不相同，一般选择较长的方向进行划分，以优化递归的效率。