最大化间隔

每周挑战 298

穆罕默德·S·安瓦尔 (Mohammad S. Anwar) 每周都会发出“每周挑战”，让我们所有人都有机会为两周的任务提出解决方案。这对我们所有人来说都是练习编码的好方法。

挑战，我的解决方案

任务 1：最大平方

任务

给你一个只有 0 和 1 的 m x n 二进制矩阵。

编写一个脚本来查找仅包含 1 的最大正方形并返回其面积。

我的解决方案

我的主要函数首先检查矩阵每行的列数是否正确

def maximal_square(matrix: list[list[int]]) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_size = 0

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

然后它会迭代矩阵中的每个单元格。如果该单元格中的项目是 1，则它会检查从该位置开始的正方形的大小。 max_side 变量也会被计算以确保我们不会超出范围。我们跟踪 Maximum_size 值并返回最大的值。

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 1:
                max_side = min(rows-row, cols-col)
                size = find_square_from_point(matrix, row, col, max_side)
                if size > maximum_size:
                    maximum_size = size

    return maximum_size

find_square_from_point 函数的正确性令人沮丧。实际上，在找到一个我很乐意提交的解决方案之前，我尝试了几次。逻辑非常简单。考虑正方形：

. b c d
b b c d
c c c d
d d d d

随着正方形尺寸的增加，我只需要检查每个正方形的底部和右侧，因为我知道正方形的内部部分已经被检查过。因此，对于第一次迭代（四个区域），我检查 b 个单元格。下一次迭代（9 的区域），我检查 c 个单元格，依此类推。

这是函数的代码：

def find_square_from_point(matrix, x: int, y: int, max_side: int) -> int:
    side = 1
    for s in range(1, max_side):
        all_ones = True
        for i in range(s+1):
            if matrix[x+i][y+s] == 0 or matrix[x+s][y+i] == 0:
                all_ones = False
                break

        if not all_ones:
            break

        side += 1

    return side ** 2

示例

$ ./ch-1.py "[[1, 0, 1, 0, 0],[1, 0, 1, 1, 1],[1, 1, 1, 1, 1],[1, 0, 0, 1, 0]]"
4

$ ./ch-1.py "[[0, 1],[1, 0]]"
1

$ ./ch-1.py "[[0]]"
0

任务 2：正确的间隔

任务

给你一个 @intervals 数组，其中 $intervals[i] = [starti, endi] 并且每个 starti 都是唯一的。

间隔 i 的正确间隔是间隔 j，使得 startj >= endi 并且 startj 最小化。请注意，i 可能等于 j。

编写一个脚本，返回每个区间 i 的右区间索引数组。如果区间 i 不存在正确的区间，则将 -1 放在索引 i 处。

我的解决方案

对于这项任务，我有一个可行的解决方案，但我不相信它是最有效的。对于每个间隔，我设置三个变量：

1. end_i 值存储我们需要考虑的结束（第二个）值
2. 值lowest_j存储迄今为止找到的最低起始值（如果没有找到则为None）。
3. index_j变量存储了lower_j值的索引，如果没有找到则为-1。

然后我有一个在间隔上迭代的内部循环。如果 start_j 值（区间中的第一个值）大于或等于 end_i 且低于 lower_j，我会更新 lower_j 和 index_j 值。

def maximal_square(matrix: list[list[int]]) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_size = 0

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

对于来自命令行的输入，我会获取一个整数列表并自动将它们配对。

示例

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 1:
                max_side = min(rows-row, cols-col)
                size = find_square_from_point(matrix, row, col, max_side)
                if size > maximum_size:
                    maximum_size = size

    return maximum_size

以上是最大化间隔的详细内容。更多信息请关注PHP中文网其他相关文章！