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