[Swift]LeetCode391.完美矩形|PerfectRectangle

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10299478.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。

每个矩形用左下角的点和右上角的点的坐标来表示。例如，一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。

示例 1:

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

返回 true。5个矩形一起可以精确地覆盖一个矩形区域。

示例 2:

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

返回 false。两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3:

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

返回 false。图形顶端留有间隔，无法覆盖成一个矩形。

示例 4:

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

返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

524ms

 1 class Solution {
 2     func isRectangleCover(_ rectangles: [[Int]]) -> Bool {
 3         var st:Set<String> = Set<String>()
 4         var min_x = Int.max
 5         var min_y = Int.max
 6         var max_x = Int.min
 7         var max_y = Int.min
 8         var area:Int = 0
 9         for rect in rectangles
10         {
11             min_x = min(min_x, rect[0])
12             min_y = min(min_y, rect[1])
13             max_x = max(max_x, rect[2])
14             max_y = max(max_y, rect[3])
15             area += (rect[2] - rect[0]) * (rect[3] - rect[1])
16             var s1:String = String(rect[0]) + "_" + String(rect[1]) // bottom-left
17             var s2:String = String(rect[0]) + "_" + String(rect[3]) // top-left
18             var s3:String = String(rect[2]) + "_" + String(rect[3]) // top-right
19             var s4:String = String(rect[2]) + "_" + String(rect[1]) // bottom-right
20             if st.contains(s1) {st.remove(s1)}
21             else {st.insert(s1)}
22             if st.contains(s2) {st.remove(s2)}
23             else {st.insert(s2)}
24             if st.contains(s3) {st.remove(s3)}
25             else {st.insert(s3)}
26             if st.contains(s4) {st.remove(s4)}
27             else {st.insert(s4)}            
28         }
29         var t1:String = String(min_x) + "_" + String(min_y)
30         var t2:String = String(min_x) + "_" + String(max_y)
31         var t3:String = String(max_x) + "_" + String(max_y)
32         var t4:String = String(max_x) + "_" + String(min_y)
33         if !st.contains(t1) || !st.contains(t2) || !st.contains(t3) || !st.contains(t4) || st.count != 4
34         {
35             return false
36         }
37         return area == (max_x - min_x) * (max_y - min_y)
38     }
39 }

1496ms

 1 class Solution {
 2             func isRectangleCover(_ rectangles: [[Int]]) -> Bool {
 3         var dic = Dictionary<String,Int>()
 4         var commenDic = Dictionary<String,Int>()
 5         //计算面积（排除覆盖）
 6         var minX = rectangles[0][0]
 7         var minY = rectangles[0][1]
 8         var maxX = rectangles[0][2]
 9         var maxY = rectangles[0][3]
10         var area:Int = 0
11         //计算角的个数
12         for i in rectangles{
13             if i[0] < minX {
14                 minX = i[0]
15             }
16             if i[1] < minY {
17                 minY = i[1]
18             }
19             if i[2] > maxX {
20                 maxX = i[2]
21             }
22             if i[3] > maxY {
23                 maxY = i[3]
24             }
25             area += (i[2]-i[0]) * (i[3]-i[1])
26 
27             let p1 = String(i[0])+","+String(i[1])
28             let p2 = String(i[0])+","+String(i[3])
29 
30             let p3 = String(i[2])+","+String(i[3])
31             let p4 = String(i[2])+","+String(i[1])
32             let pArr = [p1,p2,p3,p4]
33             for p in pArr{
34                 if let _ = dic[p]{
35                     dic[p] = nil
36                 }else{
37                     dic[p] = 1
38                 }
39             }
40             //去除遮挡
41             let p11 = p1 + ",1"
42             let p21 = p2 + ",2"
43             let p31 = p3 + ",3"
44             let p41 = p4 + ",4"
45             let pArr2 = [p11,p21,p31,p41]
46             for p in pArr2{
47                 if let _ = commenDic[p]{
48                     return false
49                 }else{
50                     commenDic[p] = 1
51                 }
52             }
53         }
54         if dic.count != 4{
55             return false
56         }
57         if area != (maxY - minY) * (maxX - minX){
58             return false
59         }
60         return true
61     }
62 }