每周挑战 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 db b c dc c c dd 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]
以上就是最大化间隔的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1354733.html
微信扫一扫 
支付宝扫一扫 
