# 1274. Number of Ships in a Rectangle

• Time: $O(\log mn)$
• Space: $O(\log mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 /** * // This is Sea's API interface. * // You should not implement it, or speculate about its implementation * class Sea { * public: * bool hasShips(vector topRight, vector bottomLeft); * }; */ class Solution { public: int countShips(Sea sea, vector topRight, vector bottomLeft) { if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1]) return 0; if (!sea.hasShips(topRight, bottomLeft)) return 0; // Sea.hashShips(topRight, bottomLeft) == true if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) return 1; const int mx = (topRight[0] + bottomLeft[0]) / 2; const int my = (topRight[1] + bottomLeft[1]) / 2; int ans = 0; // Top right ans += countShips(sea, topRight, {mx + 1, my + 1}); // Bottom right ans += countShips(sea, {topRight[0], my}, {mx + 1, bottomLeft[1]}); // Top left ans += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my + 1}); // Bottom left ans += countShips(sea, {mx, my}, bottomLeft); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * // 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) { if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1]) return 0; if (!sea.hasShips(topRight, bottomLeft)) return 0; // Sea.hashShips(topRight, bottomLeft) == true if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) return 1; final int mx = (topRight[0] + bottomLeft[0]) / 2; final int my = (topRight[1] + bottomLeft[1]) / 2; int ans = 0; // Top right ans += countShips(sea, topRight, new int[] {mx + 1, my + 1}); // Bottom right ans += countShips(sea, new int[] {topRight[0], my}, new int[] {mx + 1, bottomLeft[1]}); // Top left ans += countShips(sea, new int[] {mx, topRight[1]}, new int[] {bottomLeft[0], my + 1}); // Bottom left ans += countShips(sea, new int[] {mx, my}, bottomLeft); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 # """ # This is Sea's API interface. # You should not implement it, or speculate about its implementation # """ # class Sea(object): # def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool: # pass # # class Point(object): # def __init__(self, x: int, y: int): # self.x = x # self.y = y class Solution(object): def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int: if topRight.x < bottomLeft.x or topRight.y < bottomLeft.y: return 0 if not sea.hasShips(topRight, bottomLeft): return 0 # Sea.hashShips(topRight, bottomLeft) == True if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y: return 1 mx = (topRight.x + bottomLeft.x) // 2 my = (topRight.y + bottomLeft.y) // 2 ans = 0 # Top right ans += self.countShips(sea, topRight, Point(mx + 1, my + 1)) # Bottom right ans += self.countShips(sea, Point(topRight.x, my), Point(mx + 1, bottomLeft.y)) # Top left ans += self.countShips(sea, Point(mx, topRight.y), Point(bottomLeft.x, my + 1)) # Bottom left ans += self.countShips(sea, Point(mx, my), bottomLeft) return ans