LeetCode-391. 完美矩形(使用C语言编译,详解)

诺谦

发布于 2018-04-17 14:13:49

1.1K0

发布于 2018-04-17 14:13:49

文章被收录于专栏：Linux驱动Linux驱动

链接: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;   
}