LeetCode 题解工作台
判断网格图能否被切割成块
给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles ，其中 rectangles[i] 的格式为 [start x , start y , end x , end y ] ，表示网格图中的一个矩形。每个矩形定义如下： (st…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
class Solution: def countLineIntersections(self, coordinates: List[tuple[int, int]]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles ，其中 rectangles[i] 的格式为 [startx, starty, endx, endy] ，表示网格图中的一个矩形。每个矩形定义如下：
(startx, starty)：矩形的左下角。(endx, endy)：矩形的右上角。
注意 ，矩形相互之间不会重叠。你的任务是判断是否能找到两条 要么都垂直要么都水平 的 两条切割线 ，满足：
- 切割得到的三个部分分别都 至少 包含一个矩形。
- 每个矩形都 恰好仅 属于一个切割得到的部分。
如果可以得到这样的切割，请你返回 true ，否则返回 false 。
示例 1：
输入：n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
输出：true
解释：
网格图如上所示，我们可以在 y = 2 和 y = 4 处进行水平切割，所以返回 true 。
示例 2：
输入：n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]
输出：true
解释：
我们可以在 x = 2 和 x = 3 处进行竖直切割，所以返回 true 。
示例 3：
输入：n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]
输出：false
解释：
我们无法进行任何两条水平或者两条竖直切割并且满足题目要求，所以返回 false 。
提示：
3 <= n <= 1093 <= rectangles.length <= 1050 <= rectangles[i][0] < rectangles[i][2] <= n0 <= rectangles[i][1] < rectangles[i][3] <= n- 矩形之间两两不会有重叠。
解题思路
方法一
class Solution:
def countLineIntersections(self, coordinates: List[tuple[int, int]]) -> bool:
lines = 0
overlap = 0
for value, marker in coordinates:
if marker == 0:
overlap -= 1
else:
overlap += 1
if overlap == 0:
lines += 1
return lines >= 3
def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
y_coordinates = []
x_coordinates = []
for rect in rectangles:
x1, y1, x2, y2 = rect
y_coordinates.append((y1, 1)) # start
y_coordinates.append((y2, 0)) # end
x_coordinates.append((x1, 1)) # start
x_coordinates.append((x2, 0)) # end
# Sort by coordinate value, and for tie, put end (0) before start (1)
y_coordinates.sort(key=lambda x: (x[0], x[1]))
x_coordinates.sort(key=lambda x: (x[0], x[1]))
return self.countLineIntersections(
y_coordinates
) or self.countLineIntersections(x_coordinates)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \log n) |
| 空间 | O(S) |
面试官常问的追问
外企场景- question_mark
Notice if candidate separates x and y coordinates instead of treating rectangles as full objects.
- question_mark
Look for the candidate using sorting to quickly identify potential cuts.
- question_mark
Pay attention to whether the candidate considers gaps between rectangles rather than individual points.
常见陷阱
外企场景- error
Failing to sort coordinates before checking for gaps can miss valid cut positions.
- error
Assuming overlapping rectangles might exist despite the constraint forbidding it.
- error
Checking only horizontal or only vertical cuts without considering both possibilities.
进阶变体
外企场景- arrow_right_alt
Determine if exactly three cuts can divide the grid into four valid sections.
- arrow_right_alt
Consider rectangles that may partially overlap and find maximal non-overlapping cuts.
- arrow_right_alt
Optimize for minimal total number of cuts needed to separate all rectangles.