哈希算法题目：设计完美矩形 题目描述： 给定 N 个轴对齐的矩形，每个矩形用左下角坐标 (x1, y1) 和右上角坐标 (x2, y2) 表示。判断这些矩形是否精确地覆盖了一个矩形区域，且矩形之间不重叠（只允许相邻边接触）。 解题过程： 步骤1：理解完美矩形的条件 一个完美的矩形需要满足两个核心条件： 面积条件：所有小矩形的总面积必须等于最终大矩形的面积 顶点条件：最终大矩形只能有4个顶点出现奇数次，其他所有顶点都必须出现偶数次 步骤2：面积验证 计算所有小矩形的面积之和：sum_ area = Σ[ (x2-x1)×(y2-y1) ] 找到最终大矩形的边界：min_ x, min_ y, max_ x, max_ y 计算大矩形面积：total_ area = (max_ x-min_ x)×(max_ y-min_ y) 如果sum_ area ≠ total_ area，直接返回false 步骤3：顶点统计 使用哈希表记录每个顶点的出现次数 对于每个小矩形，处理它的4个顶点： (x1, y1), (x1, y2), (x2, y1), (x2, y2) 每个顶点出现次数+1（如果已存在）或初始化为1（如果新顶点） 步骤4：奇数次顶点检查 最终大矩形的4个角点应该出现奇数次 其他所有顶点都应该出现偶数次 如果奇数次顶点的数量不等于4，返回false 步骤5：边界验证 确保所有小矩形都在大矩形的边界内 检查是否有重叠的矩形（通过顶点分布可以间接验证） 示例演示： 输入：rectangles = [ [ 1,1,3,3], [ 3,1,4,2], [ 3,2,4,4], [ 1,3,2,4], [ 2,3,3,4] ] 步骤执行： 计算总面积：4 + 2 + 2 + 2 + 1 = 11 大矩形边界：min_ x=1, min_ y=1, max_ x=4, max_ y=4 大矩形面积：(4-1)×(4-1) = 9 ≠ 11 → 返回false 这个算法的时间复杂度是O(n)，空间复杂度是O(n)，其中n是矩形的数量。