数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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 填充
对于 i 从 0 到 col，执行
temp[0, i] := mat[0, i]
对于 j 从 1 到 row，执行
如果 mat[j, i] 等于 0，则
temp[j, i] := 0
否则，
temp[j, i] := temp[j - 1, i] + 1
对于 i 从 0 到 row，执行
cnt := 一个大小为 (row + 1) 的数组，并用 0 填充
对于 j 从 0 到 col，递增 1，执行
cnt[temp[i, j]] := cnt[temp[i, j]] + 1
col_no := 0
j := row
当 j >= 0 时，执行
如果 cnt[j] > 0，则
对于 k 从 0 到 cnt[j]，执行
temp[i, col_no] := j
col_no := col_no + 1
j := j - 1
area_maximum := 0
对于 i 从 0 到 row，执行
对于 j 从 0 到 col，执行
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
131 次查看
