穆罕默德·S·安瓦爾 (Mohammad S. Anwar) 每週都會發出“每週挑戰”，讓我們所有人都有機會為兩週的任務提出解決方案。這對我們所有人來說都是練習編碼的好方法。
挑戰，我的解決方案
給你一個只有 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
給你一個 @intervals 數組，其中 $intervals[i] = [starti, endi] 並且每個 starti 都是唯一的。
間隔 i 的正確間隔是間隔 j，使得 startj >= endi 且 startj 最小化。注意，i 可能等於 j。
寫一個腳本，傳回每個區間 i 的右區間索引陣列。如果區間 i 不存在正確的區間，則將 -1 放在索引 i 處。
對於這項任務，我有一個可行的解決方案，但我不相信它是最有效的。對於每個間隔，我設定三個變數：
然後我有一個在間隔上迭代的內部循環。如果 start_j 值（區間中的第一個值）大於或等於 end_i 且低於 lower_j，我會更新 lower_j 和 index_j 值。
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)
對於來自命令列的輸入，我會取得整數清單並自動將它們配對。
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
以上是最大化間隔的詳細內容。更多資訊請關注PHP中文網其他相關文章！
