C语言 | Leetcode C语言题解之第391题完美矩形

题目：

题解：

/* 参照官方答案题解：
1.小矩形面积之和等于大矩形区域面积
2.矩形区域内部顶点出现次数只能是2次或4次（边界四个顶点只能出现一次）
*/
typedef struct {int x;int y;
} Coordinate;typedef struct {Coordinate pos;int cnt;UT_hash_handle hh;
} CoordRecord;CoordRecord *FindNode(CoordRecord **root, int x, int y)
{Coordinate tmp = {.x = x,.y = y};CoordRecord *ptr = NULL;HASH_FIND(hh, *root, &tmp, sizeof(Coordinate), ptr);return ptr;
}void AddNode(CoordRecord **root, int x, int y)
{CoordRecord *ptr = FindNode(root, x, y);if (ptr == NULL) {CoordRecord *rec = (CoordRecord*)malloc(sizeof(CoordRecord));rec->cnt = 1;rec->pos.x = x;rec->pos.y = y;HASH_ADD(hh, *root, pos, sizeof(Coordinate), rec);} else {(ptr->cnt)++;}
}bool isRectangleCover(int** rectangles, int rectanglesSize, int* rectanglesColSize){CoordRecord *root = NULL;int minx = INT_MAX;int miny = INT_MAX;int maxa = 0;int maxb = 0;int area = 0;for (int i = 0; i < rectanglesSize; ++i) {int x = rectangles[i][0];int y = rectangles[i][1];int a = rectangles[i][2];int b = rectangles[i][3];/* 计算每个小矩形的面积之和 */area += (a - x) * (b - y);/* 为最后求大矩形面积做准备 */minx = fmin(minx, x);miny = fmin(miny, y);maxa = fmax(maxa, a);maxb = fmax(maxb, b);/* 统计每个顶点出现的次数 */AddNode(&root, x, y);AddNode(&root, x, b);AddNode(&root, a, y);AddNode(&root, a, b);}/* 面积之和不相等，则返回false */if ((maxa - minx) * (maxb - miny) != area) {return false;}/* 判断每个顶点出现的次数 */HASH_ITER(hh, root, node, p) {// 左边界两个顶点if ((node->pos.x == minx) && (node->pos.y == miny || node->pos.y == maxb)) {if (node->cnt != 1) {return false;}// 右边界两个顶点} else if ((node->pos.x == maxa) && (node->pos.y == miny || node->pos.y == maxb)) {if (node->cnt != 1) {return false;}// 内部顶点} else {if (node->cnt % 2) {return false;}}}/* 释放hash表 */HASH_ITER(hh, root, node, p) {HASH_DEL(root, node);free(node);}return true;
}