資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用Python統計全為1的正方形子矩陣的數量
假設我們有一個m x n的二進位制矩陣，我們需要找到有多少個正方形子矩陣全是1。
例如，如果輸入是：
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
那麼輸出將是15，因為有10個邊長為1的正方形，4個邊長為2的正方形和1個邊長為3的正方形。因此正方形的總數 = 10 + 4 + 1 = 15。
為了解決這個問題，我們將遵循以下步驟：
如果矩陣只有一個1，則
返回1
rows := 矩陣的行數
cols := 矩陣第一行的列數
result := 0
對於row 從0到rows - 1：
對於col 從0到cols - 1：
如果row等於0或col等於0：
如果matrix[row, col]等於1：
result := result + 1
否則，如果matrix[row, col]等於1：
square := 1 + min(matrix[row-1,col], matrix[row,col-1], matrix[row-1,col-1])
matrix[row, col] := square
result := result + square
返回result
讓我們來看下面的實現以更好地理解：
示例
def solve(matrix): if matrix == [[1]]: return 1 rows = len(matrix) cols = len(matrix[0]) result = 0 for row in range(rows): for col in range(cols): if (row == 0 or col == 0): if matrix[row][col] == 1: result += 1 elif matrix[row][col] == 1: square = min(matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1 matrix[row][col] = square result += square return result matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]] print(solve(matrix))
輸入
{{0,1,1,1},{1,1,1,1},{0,1,1,1}}輸出
15
更新於：2021年5月29日
瀏覽量：152
廣告