資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
