2022-01-21:完美矩形。
给你一个数组 rectangles ,其中 rectangles[i] = [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 } }
执行结果如下:
左神java代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)