leetcode391. Perfect Rectangle

不知名網友發布于2019-08-16 15:40 / 355人閱讀

摘要：題目要求用一個二維數組來表示一堆矩形，二維數組中的每一行分別記錄矩形左下角和右上角的坐標。該理想情況下矩形的面積應當等于所有矩形的面積之和。一旦不相等，則一定無法構成大的矩形。其次，光判斷面積并不足夠，可以這樣三個矩形構成的圖形。

題目要求

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

用一個二維數組來表示一堆矩形，二維數組中的每一行分別記錄矩形左下角和右上角的坐標。試判斷這些矩形拼接成的新的圖形是否還是一個矩形。如果矩形存在重合，則不構成矩形，見圖例4.

思路和代碼

這是一道純粹的考驗思維的一道題目。
首先我們知道，這些矩形如果能夠拼接成一個大的矩形，那么大的矩形的左下角坐標一定是所有矩形中最小的x1和y1值構成的，同理，右上角坐標一定是由最大的x2和y2的值構成的。該理想情況下矩形的面積應當等于所有矩形的面積之和。一旦不相等，則一定無法構成大的矩形。

其次，光判斷面積并不足夠，可以這樣三個矩形構成的圖形[1,1,2,2],[2,2,3,3],[2,1,3,3]。可以看到該圖形的理想矩形就是一個2*2的正方形，它的面積與所有的小矩形的和相等，但是這些小矩形并沒有構成該理想的矩形。那么我們能用什么方式來過濾掉這種矩形呢。只能從矩形的頂點入手了。
我們知道，任何一個能夠構成理想矩形的小矩形，一定會有頂點的重合，直到只剩下四個重合度為1的點，即大矩形的四個頂點。其它的所有頂點都應當有另一個矩形與其重合。因此我們只需要留下所有度為1的頂點，判斷其是否都是大矩形的四個頂點即可。

代碼如下：

public boolean isRectangleCover(int[][] rectangles) {
        if(rectangles==null || rectangles.length == 0 || rectangles[0].length == 0) return false;
        int areaSum = 0;
        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MIN_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MIN_VALUE;
        
        Set points = new HashSet<>(rectangles.length * 4);
        for(int[] rectangle : rectangles) {
            x1 = Math.min(rectangle[0], x1);
            x2 = Math.max(rectangle[2], x2);
            y1 = Math.min(rectangle[1], y1);
            y2 = Math.max(rectangle[3], y2);
            
            areaSum += (rectangle[0] - rectangle[2]) * (rectangle[1] - rectangle[3]);
            String s1 = rectangle[0] + " " + rectangle[1];
            String s2 = rectangle[0] + " " + rectangle[3];
            String s3 = rectangle[2] + " " + rectangle[1];
            String s4 = rectangle[2] + " " + rectangle[3];
            if (!points.add(s1)) {
                points.remove(s1);
            }
            if (!points.add(s2)) {
                points.remove(s2);
            }
            if (!points.add(s3)) {
                points.remove(s3);
            }
            if (!points.add(s4)) {
                points.remove(s4);
            }
        }
        if(!points.contains(x1 + " " + y1) || 
                !points.contains(x1 + " " + y2) ||
                !points.contains(x2 + " " + y1) ||
                !points.contains(x2 + " " + y2) ||
                points.size() != 4) return false;
        return areaSum == (x2 - x1) * (y2 - y1);
    }

云服務器 GPU云服務器 perfect Rectangle Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73628.html

Perfect Rectangle

摘要：首先確定上下的邊界，左右線段按照橫坐標排序。檢查填充滿上圖的情況就組成不了一個長方形。找重合和有空隙只需要把所有橫坐標在的線段排序之后檢查首位相連，且起點，終點。且最后成的面積等于小矩形的面積和。 Perfect Rectangle 題目鏈接：https://leetcode.com/problems... 掃描線，哪個方向都行。我是從左往右掃，矩陣按照左右的邊來存。showImg(h...

SolomonXie 2019-08-14 17:23 評論0 收藏0
[LC] Perfect Rectangle / Find the Difference / Eli

Find the Difference User Accepted: 812User Tried: 861Total Accepted: 1362Total Submissions: 1552Difficulty: Easy Given two strings s and t which consist of only lowercase letters. String t is generate...

mingde 2019-08-14 14:33 評論0 收藏0
[Leetcode] Perfect Squares 完美平方數

摘要：動態規劃復雜度時間空間思路如果一個數可以表示為一個任意數加上一個平方數，也就是，那么能組成這個數最少的平方數個數，就是能組成最少的平方數個數加上因為已經是平方數了。 Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4...

Moxmi 2019-08-14 12:33 評論0 收藏0
[LeetCode] 367. Valid Perfect Square

Problem Given a positive integer num, write a function which returns True if num is a perfect square else False. Example For example:Given num = 16Returns True Solution class Solution { public boo...

sean 2019-08-15 18:08 評論0 收藏0
[LeetCode] 279. Perfect Squares

Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Exampl...

mist14 2019-08-16 13:57 評論0 收藏0