(Leetcode)完美矩形

Question

这是一个Leetcode问题 -

给定N轴对齐矩形( N > 0__ )，确定它们是否一起构成矩形区域的精确覆盖。每个矩形都表示为左下角和右上角.例如，单位方格表示为[1, 1, 2, 2]__。(左下角的坐标为(1, 1)，右上点为(2, 2)__)。示例1-矩形=[ 1，1，3，3，3、1、4、2，3，2，4，4，1，3，2，4，2，3，3，4 ]#解释-返回真。所有5个矩形一起形成一个矩形区域的精确覆盖。

示例2-矩形=[ 1，1，2，3，1，3，2，4，3、1、4、2，3，2，4，4 ]#解释-返回False。因为两个矩形区域之间有一个缺口。

示例3-矩形=[ 1，1，3，3，3、1、4、2，1，3，2，4，3，2，4，4 ]#解释-返回False。因为顶端的中锋有个缺口。

示例4-矩形=[ 1，1，3，3，3、1、4、2，1，3，2，4，2，2，4，4 ]#解释-返回False。因为两个矩形互相重叠。

这是我对这个挑战的解决方案-

def is_rectangle_cover(rectangles):

    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1 = float("inf")
    y1 = float("inf")
    x2 = 0
    y2 = 0
    rect = set()
    area = 0
    for points in rectangles:
        x1 = min(points[0], x1)
        y1 = min(points[1], y1)
        x2 = max(points[2], x2)
        y2 = max(points[3], y2)
        area += (points[3] - points[1]) * (points[2] - points[0])
        rect.remove((points[0], points[3])) if (points[0], points[3]) in rect else rect.add((points[0], points[3]))
        rect.remove((points[0], points[1])) if (points[0], points[1]) in rect else rect.add((points[0], points[1]))
        rect.remove((points[2], points[3])) if (points[2], points[3]) in rect else rect.add((points[2], points[3]))
        rect.remove((points[2], points[1])) if (points[2], points[1]) in rect else rect.add((points[2], points[1]))
    if (x1, y2) not in rect or (x2, y1) not in rect or (x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
        return False
    return area == (y2 - y1) * (x2 - x1) 

以下是每个示例输出所需的时间-

示例1 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]])

14.9 µs ± 117 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

示例2 -

# %timeit is_rectangle_cover([[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2],[3, 2, 4, 4]])

12.5 µs ± 494 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

示例3 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]])

12.4 µs ± 195 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

示例4 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]])

12 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

这是我46个测试用例的代码结果-

因此，我想知道我是否可以使这个程序更短，更有效率。

任何帮助都将不胜感激。

Answer 1

使用元组

当数据不可变时，列表的...instead。有一些优点，包括在某些场景中性能略有提高，以及代码试图在不应该修改数据的地方修改数据的“惊喜”。

解压缩您的元组

索引points是很讨厌的。

使用更多的集

我认为我用集合运算符重写的代码是等价的。仔细阅读文献资料获取关于对称差分^和子集<运算符的信息。

编辑:您甚至不需要子集测试，只需要设置相等。

不要“三元”而不是“if"

即使您没有执行对称的set操作并保留添加/删除代码，只要.别这么做。这是“太聪明”、“太难读”和“很难维持”的最糟糕的组合。

合并您的返回

为了简单起见，...into一个布尔语句。

提出的

def is_rectangle_cover_orig(rectangles):
    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1 = float("inf")
    y1 = float("inf")
    x2 = 0
    y2 = 0
    rect = set()
    area = 0
    for points in rectangles:
        x1 = min(points[0], x1)
        y1 = min(points[1], y1)
        x2 = max(points[2], x2)
        y2 = max(points[3], y2)
        area += (points[3] - points[1]) * (points[2] - points[0])
        rect.remove((points[0], points[3])) if (points[0], points[
            3]) in rect else rect.add((points[0], points[3]))
        rect.remove((points[0], points[1])) if (points[0], points[
            1]) in rect else rect.add((points[0], points[1]))
        rect.remove((points[2], points[3])) if (points[2], points[
            3]) in rect else rect.add((points[2], points[3]))
        rect.remove((points[2], points[1])) if (points[2], points[
            1]) in rect else rect.add((points[2], points[1]))
    if (x1, y2) not in rect or (x2, y1) not in rect or \
            (x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
        return False
    return area == (y2 - y1) * (x2 - x1)


def is_rectangle_cover_new(rectangles):
    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1, y1 = float("inf"), float("inf")
    x2, y2 = 0, 0
    rect = set()
    area = 0
    for xr1, yr1, xr2, yr2 in rectangles:
        x1 = min(xr1, x1)
        y1 = min(yr1, y1)
        x2 = max(xr2, x2)
        y2 = max(yr2, y2)
        area += (yr2 - yr1) * (xr2 - xr1)
        rect ^= {(xr1, yr2), (xr1, yr1), (xr2, yr2), (xr2, yr1)}
    return (
        rect == {(x1, y2), (x2, y1), (x1, y1), (x2, y2)} and
        area == (y2 - y1) * (x2 - x1)
    )


def test():
    for i, rects in enumerate((
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (3, 2, 4, 4),
            (1, 3, 2, 4),
            (2, 3, 3, 4)
        ),
        (
            (1, 1, 2, 3),
            (1, 3, 2, 4),
            (3, 1, 4, 2),
            (3, 2, 4, 4)
        ),
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (1, 3, 2, 4),
            (3, 2, 4, 4)
        ),
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (1, 3, 2, 4),
            (2, 2, 4, 4)
        )
    ), 1):
        old_ans = is_rectangle_cover_orig(rects)
        new_ans = is_rectangle_cover_new(rects)
        print(f'Example {i}: {old_ans}')
        assert old_ans == new_ans


test()