元宝DeepSeek LeetCode 391.完美矩形 public boolean isRectangleCover(int[][] rectangles)
·
对于 LeetCode 391 完美矩形问题,需要判断一组矩形是否恰好无重叠无遗漏地覆盖一个矩形区域。关键条件是:所有小矩形的总面积等于最终大矩形的面积,且只有大矩形的四个顶点出现奇数次,其余顶点均出现偶数次。
以下是 Java 实现,采用顶点奇偶性统计和面积校验:
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
long sumArea = 0;
Set points = new HashSet<>();
for (int[] rect : rectangles) {
int x = rect[0], y = rect[1], a = rect[2], b = rect[3];
minX = Math.min(minX, x);
minY = Math.min(minY, y);
maxX = Math.max(maxX, a);
maxY = Math.max(maxY, b);
sumArea += (long)(a - x) * (b - y);
long[] corners = {encode(x, y), encode(a, y), encode(a, b), encode(x, b)};
for (long corner : corners) {
if (points.contains(corner)) points.remove(corner);
else points.add(corner);
}
}
long totalArea = (long)(maxX - minX) * (maxY - minY);
if (sumArea != totalArea) return false;
if (points.size() != 4) return false;
long[] expected = {encode(minX, minY), encode(minX, maxY),
encode(maxX, minY), encode(maxX, maxY)};
for (long e : expected) {
if (!points.contains(e)) return false;
}
return true;
}
private long encode(int x, int y) {
return ((long)x << 32) | (y & 0xFFFFFFFFL);
}
}
该算法遍历一次矩形数组,计算总面积和顶点奇偶性,最后校验面积和顶点,时间复杂度 O(n),空间复杂度 O(n)。
更多推荐


所有评论(0)