在 Python 中,使用允许的列交换功能查找 1 的最大矩形
假设我们有一个二元矩阵,我们必须找到该给定矩阵中所有 1 的最大矩形。可以通过交换或交换该矩阵的任意一对列来构建矩形。
因此,如果输入如下
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
那么在这种情况下输出将是 6。可以通过将第 1 列与第 3 列交换来生成矩形。交换后的矩阵将是 −
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
为了解决这个问题,我们将遵循以下步骤 −
row := mat 的大小
col := mat[0] 的大小
temp := 一个顺序为 (row + 1) x (col + 1) 的矩阵,并用 0 填充
对于范围从 0 到 col 的 i,执行
temp[0, i] := mat[0, i]
对于范围从 1 到 row 的 j,执行
如果 mat[j, i] 与 0 相同,则
temp[j, i] := 0
否则,
temp[j, i] := temp[j - 1, i] + 1
对于范围从 0 到 row 的 i,执行
cnt := 一个大小为 (row + 1) 的数组,并用 0 填充
对于范围从 0 到 col 的 j,增加 1,执行
cnt[temp[i, j]] := cnt[temp[i, j]] + 1
col_no := 0
j := row
当 j >= 0 时,执行
如果 cnt[j] > 0,然后
对于范围从 0 到 cnt[j] 的 k,执行
temp[i, col_no] := j
col_no := col_no + 1
j := j - 1
area_maximum := 0
对于范围从 0 到 row 的 i,执行
对于范围从 0 到 col 的 j,执行
area_current :=(j + 1) * temp[i, j]
如果 area_current > area_maximum,则
area_maximum := area_current
返回 area_maximum
示例
让我们看看下面的实现以便更好地理解 −
def maxArea(mat):
row = len(mat)
col = len(mat[0])
temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
for i in range(0, col):
temp[0][i] = mat[0][i]
for j in range(1, row):
if ((mat[j][i] == 0)):
temp[j][i] = 0
else:
temp[j][i] = temp[j - 1][i] + 1
for i in range(0, row):
cnt = [0 for i in range(row + 1)]
for j in range(0, col, 1):
cnt[temp[i][j]] += 1
col_no = 0
j = row
while(j >= 0):
if (cnt[j] > 0):
for k in range(0, cnt[j]):
temp[i][col_no] = j
col_no += 1
j -= 1
area_maximum = 0
for i in range(0, row):
for j in range(0, col):
area_current = (j + 1) * temp[i][j]
if (area_current > area_maximum):
area_maximum = area_current
return area_maximum
mat = [
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 1, 1, 0]]
print("Area : ",maxArea(mat))
输入
[ [1, 0, 0, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]]
输出
Area : 2
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

