手记

LeetCode 矩阵重叠

矩阵重叠


题目


矩形以列表 [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 轴默认指向上。
  • 你可以仅考虑矩形是正放的情况。

解题思路


思路:逆向思维,检查两个矩阵的相对位置。

虽然本题要求的是两个矩阵是否有重叠的部分,但同时可以反过来思考,两个矩阵在什么情况下不会重叠。那么排除不重叠的情况,那剩下的则是重叠的情况。

在本题中,可以考虑两个矩阵的相对位置。假设先固定其中一个矩阵 rec1,现在考虑在什么情况下,另外一个矩阵 rec2 不会与当前矩阵重叠。

rec1 固定时,只要 rec2 出现在 rec1 的四个方向,也就是说,满足下面的至少一种,则两者不会重叠:

  1. rec2rec1 的上方;
  2. rec2rec1 的右侧;
  3. rec2rec1 的下方;
  4. rec2rec1 的左侧。

在这里,具体如何定义四个方向?【上方】表示的是,可以找到一条平行于 x 轴的线(这里线可以跟矩阵的边重合,题目有提及)将两个矩阵分隔开。【右侧】、【下方】和【左侧】同理。

现在已经可以明确,只要出现上面情况中至少一种,两个矩阵都不会重合。那么现在考虑,如何将这四种情况,转换为明确的表达式。

根据题意,矩阵是以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。

那么先将矩阵 rec1 对应的列表,解压赋值给 x1, y1, x2, y2;将矩阵 rec2 对应的列表,解压赋值给 x3, y3, x4, y4

对于 rec2rec1 的上方这种情况,表示矩阵 rec2 在 y 轴上的最小值,要大于矩阵 rec1 在 y 轴上的最大值。另外三种情况同理,如下面的表达式:

  1. 【上方】: y3 >= y2
  2. 【右侧】: x3 >= x2
  3. 【下方】: y4 <= y1
  4. 【左侧】: x4 <= x1

代码实现


class Solution(object):
    def isRectangleOverlap(self, rec1, rec2):
    	# 解压赋值
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        # 符合下面 4 中情况的至少一种就表示不重合
        # 题意要求重叠部分,这里不重合所以返回 False
        if y3 >= y2 or x3 >= x2 or y4 <= y1 or x1 >= x4:
            return False
        return True

实现效果



以上就是使用逆向思维,考虑两个矩阵相对位置如何不重叠的情况逆向解决《矩阵重叠》问题的主要内容。

1人推荐
随时随地看视频
慕课网APP