Leetcode 836:矩形重叠(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 836:矩形重叠(超详细的解法!!!)

in leetcode with 0 comment

矩形以列表[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. 两个矩形rec1rec2都以含有四个整数的列表的形式给出。
  2. 矩形中的所有坐标都处于-10^910^9之间。

解题思路

如果两个矩形相交,那么两者左边横坐标的最大值一定小于两者右边横坐标的最小值,两者下边纵坐标的最大值一定小于两者上边纵坐标的最小值。

class Solution:
    def isRectangleOverlap(self, r1: List[int], r2: List[int]) -> bool:
        return max(r1[0], r2[0]) < min(r1[2], r2[2]) and max(r1[1], r2[1]) < min(r1[3], r2[3])

如果将上面这个式子展开就可以得到:

其中1、4、5、8显然成立,所以只要满足$r1[0] < r2[2] \& r1[1] < r2[3] \& r2[0] > r1[2] \& r2[1] < r1[3]$即可。

class Solution:
    def isRectangleOverlap(self, r1: List[int], r2: List[int]) -> bool:
        return r1[0] < r2[2] and r1[1] < r2[3] and r1[2] > r2[0] and r1[3] > r2[1]

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses