LeetCode_矩形_困难_391.完美矩形

雨点打透心脏的1/2处 2023-10-06 22:28 35阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个数组 rectangles ，其中 rectangles\[i\] = \[xi, yi, ai, bi\] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true；否则，返回 false 。

**示例 1：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16]  
输入：rectangles = \[\[1,1,3,3\],\[3,1,4,2\],\[3,2,4,4\],\[1,3,2,4\],\[2,3,3,4\]\]  
输出：true  
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

**示例 2：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16 1]  
输入：rectangles = \[\[1,1,2,3\],\[1,3,2,4\],\[3,1,4,2\],\[3,2,4,4\]\]  
输出：false  
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

**示例 3：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16 2]  
输入：rectangles = \[\[1,1,3,3\],\[3,1,4,2\],\[1,3,2,4\],\[2,2,4,4\]\]  
输出：false  
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

**提示：**  
1 <= rectangles.length <= 2 \* 104  
rectangles\[i\].length == 4  
\-105 <= xi, yi, ai, bi<= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/perfect-rectangle

## 2.思路 ##

（1）哈希表  
思路见[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————哈希表
    class Solution {
        
        public boolean isRectangleCover(int[][] rectangles) {
        
            long area = 0;
            int minX = rectangles[0][0], minY = rectangles[0][1], maxX = rectangles[0][2], maxY = rectangles[0][3];
            Map<Point, Integer> cnt = new HashMap<Point, Integer>();
            for (int[] rect : rectangles) {
        
                int x = rect[0], y = rect[1], a = rect[2], b = rect[3];
                area += (long) (a - x) * (b - y);
    
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);
                maxX = Math.max(maxX, a);
                maxY = Math.max(maxY, b);
    
                Point point1 = new Point(x, y);
                Point point2 = new Point(x, b);
                Point point3 = new Point(a, y);
                Point point4 = new Point(a, b);
    
                cnt.put(point1, cnt.getOrDefault(point1, 0) + 1);
                cnt.put(point2, cnt.getOrDefault(point2, 0) + 1);
                cnt.put(point3, cnt.getOrDefault(point3, 0) + 1);
                cnt.put(point4, cnt.getOrDefault(point4, 0) + 1);
            }
    
            Point pointMinMin = new Point(minX, minY);
            Point pointMinMax = new Point(minX, maxY);
            Point pointMaxMin = new Point(maxX, minY);
            Point pointMaxMax = new Point(maxX, maxY);
            if (area != (long) (maxX - minX) * (maxY - minY) || cnt.getOrDefault(pointMinMin, 0) != 1 || cnt.getOrDefault(pointMinMax, 0) != 1 || cnt.getOrDefault(pointMaxMin, 0) != 1 || cnt.getOrDefault(pointMaxMax, 0) != 1) {
        
                return false;
            }
    
            cnt.remove(pointMinMin);
            cnt.remove(pointMinMax);
            cnt.remove(pointMaxMin);
            cnt.remove(pointMaxMax);
    
            for (Map.Entry<Point, Integer> entry : cnt.entrySet()) {
        
                int value = entry.getValue();
                if (value != 2 && value != 4) {
        
                    return false;
                }
            }
            return true;
        }
    }
    
    class Point {
        
        int x;
        int y;
    
        public Point(int x, int y) {
        
            this.x = x;
            this.y = y;
        }
    
        @Override
        public int hashCode() {
        
            return x + y;
        }
    
        @Override
        public boolean equals(Object obj) {
        
            if (obj instanceof Point) {
        
                Point point2 = (Point) obj;
                return this.x == point2.x && this.y == point2.y;
            }
            return false;
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/39e64a32f4444bf7a56c60e6d8649180.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/d54f8e82e64448e195b9a0c51575f0f0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu_size_12_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d253d2079341450398e07c510d22ab84.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA55Oi5rGf5rmW5oiR5rKJ5rWu,size_12,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://leetcode-cn.com/problems/perfect-rectangle/solution/wan-mei-ju-xing-by-leetcode-solution-ty8q/