20200502
Plan
leetcode 每日一题
Notes
- 矩形重叠 矩形以列表 [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
这道题刚开始在纸上画矩阵画了很久，但是发现边界条件比较复杂，看了题解，发现如下两种非常好用的方法：
1.逆向思维 刚开始只想着如何找两个矩阵重叠，但是如果找不重叠的话，就简单很多。假设一个矩阵rec1,那么rec2与rec1不重叠也就是如下四种情况： （1）rec2在rec1左边。 （2）rec2在rec1右边。 （3）rec2在rec1上边。 （4）rec2在rec1下边。 假设rec1的左下坐标为(x1,y1),右上坐标为(x2,y2); 假设rec2的左下坐标为(i1,j1),右上坐标为(i2,j2);
将上述情况转换成程序语言： （1）rec2在rec1左边--->i2<=x1 （2）rec2在rec1右边--->i1>=x2 （3）rec2在rec1上边--->j1>=y2 （4）rec2在rec1下边--->j2<=y1 上面四种情况都是不重叠的，其他情况就是重叠的情况。
2.投影法 如果两个矩阵重叠，那么他们在x轴上的投影一定相交，且在y轴上的投影一定相交。用程序语言表达如下： （1）在x轴上的投影相交--->min(x2,i2)>max(x1,i1) （2）在y轴上的投影相交--->min(y2,j2)>max(y1,j1) 同时满足上述两种情况即重叠。