2022-01-21：完美矩形。给你一个数组 rectangles ，其中

原创

福大大架构师每日一题

发布于 2022-01-21 22:33:38

3410

发布于 2022-01-21 22:33:38

文章被收录于专栏：福大大架构师每日一题

2022-01-21：完美矩形。

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

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

力扣391。

答案2022-01-21：

条件一：四个顶点出现一次，其他点出现偶数次。

条件二：小矩形面积之和是否等于四个顶点的矩形之和。

满足这两个条件，就返回true。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    m := [][]int{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}
    ret := isRectangleCover(m)
    fmt.Println(ret)
}

func isRectangleCover(matrix [][]int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    l := math.MaxInt64
    r := math.MinInt64
    d := math.MaxInt64
    u := math.MinInt64
    map0 := make(map[int]map[int]int)
    area := 0
    for _, rect := range matrix {
        add(map0, rect[0], rect[1])
        add(map0, rect[0], rect[3])
        add(map0, rect[2], rect[1])
        add(map0, rect[2], rect[3])
        area += (rect[2] - rect[0]) * (rect[3] - rect[1])
        l = getMin(rect[0], l)
        d = getMin(rect[1], d)
        r = getMax(rect[2], r)
        u = getMax(rect[3], u)
    }
    return checkPoints(map0, l, d, r, u) && area == (r-l)*(u-d)
}

func add(map0 map[int]map[int]int, row, col int) {
    if _, ok := map0[row]; !ok {
        map0[row] = make(map[int]int)
    }
    map0[row][col]++
}

func checkPoints(map0 map[int]map[int]int, l, d, r, u int) bool {
    if map0[l][d] != 1 || map0[l][u] != 1 || map0[r][d] != 1 || map0[r][u] != 1 {
        return false
    }
    delete(map0[l], d)
    delete(map0[l], u)
    delete(map0[r], d)
    delete(map0[r], u)
    for key, _ := range map0 {
        for _, value := range map0[key] {
            if (value & 1) != 0 {
                return false
            }
        }
    }
    return true
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func getMin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

执行结果如下：