链接:
https://leetcode-cn.com/problems/perfect-rectangle/description/
题目
我们有 N 个与坐标轴对齐的矩形, 其中 N> 0, 判断它们是否能精确地覆盖一个矩形区域
每个矩形用左下角的点和右上角的点的坐标来表示例如, 一个单位正方形可以表示为 [1,1,2,2] ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )
思路
首先, rectangles[][] 数组里保存的每个小矩形, 都有 4 个角.
以示例 4 的 rectangles[0] 矩形的左下角为例:
因为 rectangles[0] 等于 {1,1,3,3}, 所以左下角为 (1,1), 处于的位置为 {0,1}
所以, 下面程序便通过一个 method[4][2] 数组来存储 4 个角度的标志位, 方便调用 4 个角出来:
int method[4][2]={{0,1},{2,3},{0,3},{2,1}}; // 左下, 右上, 左上, 右下
由于需要多个小矩形凑成的大矩形, 且不能有相交区域, 所以应该共有 4 个独立的角
比如示例 1, 就有 4 个独立的角:
而示例 4, 有相交区域, 所以不止超过 4 个独立的角:
除了计算独立的角以外, 还要计算矩形是否重叠过, 以及核对矩形面积.
比如下例所示, 同样, 也是 4 个独立的角, 不仅有相交区域, 而且还不是一个矩形区域:
- rectangles = [
- [1,1,3,2],
- [1,1,3,2],
- [1,3,3,4],
- ]
绘制成图后:
所以在代码里, 需要定义 2 个数组
一个用来存储角的位置, 以及左下, 右上, 左上, 右下的标志位
另一个用来存储矩形区域的 left,low,right,top 的范围, 用来核对面积用
当我们每取出来一个角, 都需要去匹配是否与以前的角重叠, 为了效益需要用到 Hash 表, C 语言没有 Hash 表函数, 所以我们还需要自己来编写 Hash 表函数
代码如下:
- #define AREA(rectang)((rectang[3] - rectang[1]) * (rectang[2] - rectang[0]))#define Index(x, y, Hashlen)((x * x + y * y) % Hashlen) void Hash_Init(int Hash[][8], int len) {
- for (int i = 0; i <len; i++) {
- Hash[i][7] = 0;
- }
- }
- // 首先查找表, 如果存在, 则检查该角度是否被重叠, 如果不存在, 则插入表
- bool Hash_search_insert(int Hash[][8], int x, int y, int angle, int * angles, int len) {
- int addr = Index(x, y, len); // 求哈希地址
- int tmp = addr;
- // 查找
- while (Hash[addr][7] == 1) {
- if (Hash[addr][0] == x && Hash[addr][1] == y) // 已找到
- {
- if (Hash[addr][angle] == 0) // 未重叠
- {
- if (Hash[addr][6] == 0) // 是否 合并 过
- {
- Hash[addr][6] = 1; ( * angles)--;
- }
- Hash[addr][angle] = 1; // 设为占用
- return true;
- } else // 已重叠
- return false;
- }
- addr = (addr + 1) % len;
- if (addr == tmp) // 未找到
- return false;
- }
- //Hash[addr][7] 等于 0, 说明没找到, 则插入表
- Hash[addr][7] = 1;
- Hash[addr][0] = x;
- Hash[addr][1] = y;
- Hash[addr][6] = 0; // 未合并过
- ( * angles)++;
- for (int i = 2; i < 6; i++) // 左下, 右上, 左上, 右下
- if (i == angle) Hash[addr][i] = 1;
- else Hash[addr][i] = 0;
- return true;
- }
- bool isRectangleCover(int * *rectangles, int rectanglesRowSize, int rectanglesColSize) {
- int i,
- j,
- k,
- angle = 0,
- cnt = 0;
- int Hashlen = rectanglesRowSize * 8;
- int s[Hashlen][8]; // x y 左下, 右上, 左上, 右下 是否被合并 是否被使用
- int method[4][2] = {
- {
- 0,
- 1
- },
- {
- 2,
- 3
- },
- {
- 0,
- 3
- },
- {
- 2,
- 1
- }
- }; // 左下, 右上, 左上, 右下
- int Rectangles[4] = {
- 999999,
- 999999,
- -999999,
- -9999999
- }; // 大矩形 left,low,right,top
- unsigned long long Area; // 大矩形面积
- unsigned long long Fact_Area = 0; // 实际面积
- int tmp[2]; // 用来获取角的位置
- Hash_Init(s, Hashlen);
- for (i = 0; i < rectanglesRowSize; i++) {
- Fact_Area += AREA(rectangles[i]);
- for (j = 0; j < 4; j++) {
- if (j < 2) // 计算 left,low
- {
- if (Rectangles[j]> rectangles[i][j]) Rectangles[j] = rectangles[i][j];
- } else if (Rectangles[j] < rectangles[i][j]) // 计算 right,top
- Rectangles[j] = rectangles[i][j];
- tmp[0] = rectangles[i][method[j][0]];
- tmp[1] = rectangles[i][method[j][1]];
- if (!Hash_search_insert(s, tmp[0], tmp[1], j + 2, &angle, Hashlen)) return false;
- }
- }
- if (angle != 4) return false;
- Area = AREA(Rectangles);
- //printf("angle%d,Fact_Area%ld,Area%ld\n",angle,Fact_Area,Area);
- if (Fact_Area == Area) // 核对面积
- return true;
- else
- return false;
- }
来源: https://www.cnblogs.com/lifexy/p/8683020.html