LeetCode題組：第836題-矩形疊加

• 2020 年 4 月 10 日
• 筆記

1.題目

難度：簡單

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 為左下角的坐標，(x2, y2) 是右上角的坐標。如果相交的面積為正，則稱兩矩形重疊。需要明確的是，只在角或邊接觸的兩個矩形不構成重疊。給出兩個矩形，判斷它們是否重疊並返回結果。

示例 1：

輸入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 輸出：true

示例 2：

輸入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 輸出：false

提示：

兩個矩形 rec1 和 rec2 都以含有四個整數的列表的形式給出。 矩形中的所有坐標都處於 -10^9 和 10^9 之間。 x 軸默認指向右，y 軸默認指向上。 你可以僅考慮矩形是正放的情況。

2.我的解答

此題如果逆向思考什麼時候不重疊將會簡單許多。

bool isRectangleOverlap(int* rec1, int rec1Size, int* rec2, int rec2Size){      if (rec2[2] <= rec1[0]) {          return false;      }      if (rec2[0] >= rec1[2]) {          return false;      }      if (rec2[1] >= rec1[3]) {          return false;      }      if (rec2[3] <= rec1[1]) {          return false;      }      return true;  }

3.我的誤區

以下為錯誤解答

首先，我採用了暴力的解法，正面思考什麼情況下會出現重疊區，這樣導致情況複雜化很容易的就漏掉情況，十分耗時。其次，我程式碼中使用了rec1[2]>rec2[0]>rec1[0]C語言是不支援這種寫法的，需要改成rec1[2]>rec2[0]&&rec2[0]>rec1[0]。（13>10>4，13>10是對的為正，即1，所以原語句會被編譯器理解為，1>4）

bool isRectangleOverlap(int* rec1, int rec1Size, int* rec2, int rec2Size){      //重疊分四種情況討論      //右上角rec[2],rec[3]      //右下角rec[2],rec[1]      //左下角rec[0],rec[1]      //左上角rec[0],rec[3]      //1.矩形1的右上角與矩形2的左下角為重疊部分頂點      if(rec1[2]>rec2[0]>rec1[0]&&rec1[3]>rec2[1]>rec1[1]) return true;      //2.矩形1的右下角與矩形2的左上角為重疊部分頂點      if(rec1[2]>rec2[0]>rec1[0]&&rec1[1]<rec2[3]<rec1[3]) return true;      //3.矩形1的左下角與矩形2的右上角為重疊部分頂點      if(rec1[0]<rec2[2]<rec1[2]&&rec1[1]<rec2[3]<rec1[3]) return true;      //4.矩形1的左上角與矩形2的右下角為重疊部分頂點      if(rec1[0]<rec2[2]<rec1[0]&&rec1[3]>rec2[1]<rec1[1]) return true;      return false;  }