最大化间隔-Python教程-PHP中文网

最大化间隔

聖光之護

发布： 2024-12-08 22:24:01

转载

420人浏览过

最大化间隔

每周挑战 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 处。

我的解决方案

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

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

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

def right_interval(intervals: list[list[int]]) -> list:
    best_intervals = []
    for i in intervals:
        # calculate the right interval for this interval
        end_i = i[1]
        lowest_j = none
        index_j = -1
        for j in range(len(intervals)):
            start_j = intervals[j][0]
            if start_j >= end_i:
                if lowest_j is none or start_j < lowest_j:
                    # this is the best matching interval
                    lowest_j = start_j
                    index_j = j

        best_intervals.append(index_j)

    return best_intervals

登录后复制

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

示例

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

$ ./ch-2.py 1 4 2 3 3 4
[-1, 2, -1]

$ ./ch-2.py 1 2
[-1]

$ ./ch-2.py 1 4 2 2 3 4
[-1, 1, -1]

登录后复制

以上就是最大化间隔的详细内容，更多请关注php中文网其它相关文章！