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