本文主要是介绍836. Rectangle Overlap,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
836. 矩形重叠
矩形以列表
[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
之间。
解法一
//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {return rec1[0] < rec2[2] && rec2[0] < rec1[2] &&rec1[1] < rec2[3] && rec2[1] < rec1[3];}
};
用了一个潜在的规律,第一次见到还是很难想到。
最初想的是找出所有相交的情况,然后找出所有相交情况的共同点做为判据,但是相交的情况分类太多了,不好找规律。所以我们要换个思路,如下。
两个矩形不相交有两种情况:要么两矩形是“上-下”的位置关系,要么是“左-右”的位置关系(两种可以同时满足)。
上-下:(按谁在上分,有两种情况,这里只画一种):_ _ __________ (x2,y2)_ _ _ _ _ _ _ _ _| |_ _|__________| _ _ _ _ _ _ _ _ _ _ _ _
(x1,y1) __________ (x4,y4)| ||__________|(x3,y3) 左-右:(按谁在左分,也两种情况,这里只画一种)|__________|(x2,y2)| | ___________ (x4,y4)|__________| | |
(x1,y1) | |___________|| | (x3,y3)
上面的情况都满足关系
y1 >= y4 或 y2 <= y3 (上-下)或 x2 <= x3 或 x4 <= x1 (左-右)
那除了以上的情况,就都是相交了,如下:
y1 < y4 且 y2 > y3 (上-下)且 x2 > x3 且 x4 > x1 (左-右)
直接返回以上结果。
思考这个题时很容易犯一个常见的逻辑错误,就是没搞清楚判据是否是充分必要的。例如,满足一个条件可以判定两矩形相交,但是不满足这个条件,不一定能说明这两个矩形不相交。所以在找规律的时候一定要包括所有情况,不多不少。
这篇关于836. Rectangle Overlap的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!