链接: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%ldn",angle,Fact_Area,Area); if(Fact_Area==Area) //核对面积 return true; else
return false; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
