class Solution {
public:
vector<int> findSquare(vector<vector<int>>& matrix) {
}
};
面试题 17.23. 最大黑方阵
给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1:
输入: [ [1,0,1], [0,0,1], [0,0,1] ] 输出: [1,0,2] 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:
输入: [ [0,1,1], [1,0,1], [1,1,0] ] 输出: [0,0,1]
提示：
matrix.length == matrix[0].length <= 200原站题解
typescript 解法, 执行用时: 136 ms, 内存消耗: 52.5 MB, 提交时间: 2023-04-22 11:36:38
function findSquare(matrix: number[][]): number[] {
// 这道题可以这样用
// 求出每个点的向右和向下最长距离。
// 然后确定构成矩阵的size，然后查看[i,j]这个点的[i+size-1,j]的右长度有没有大于size
// 查看[i,j+size-1]这个点的下长度有没有大于size，大于就更新result
let result = [0, 0, 0];
let n = matrix.length;
let m = matrix[0].length;
let dp: number[][][] = new Array(n)
.fill(0)
.map((val) => new Array(m).fill(0).map((val) => new Array(2).fill(0)));
// ij的右边0的数量
// dp[i][j][0]=dp[i][j+1][0]+1
// ij的下边0的数量
// dp[i][j][1]=dp[i+1][j][1]+1;
dp[n - 1][m - 1][0] = matrix[n - 1][m - 1] == 0 ? 1 : 0;
dp[n - 1][m - 1][1] = matrix[n - 1][m - 1] == 0 ? 1 : 0;
// 求右边，所以必须先初始化最后一列的右边
for (let i = 0; i < n; i++) dp[i][m - 1][0] = matrix[i][m - 1] == 0 ? 1 : 0;
for (let i = 0; i < n; i++) {
for (let j = m - 2; j >= 0; j--) {
if (matrix[i][j] == 0) dp[i][j][0] = dp[i][j + 1][0] + 1;
}
}
// 求下边，所以必须先初始化最后一行的下边
for (let j = 0; j < m; j++) dp[n - 1][j][1] = matrix[n - 1][j] == 0 ? 1 : 0;
for (let j = 0; j < m; j++) {
for (let i = n - 2; i >= 0; i--) {
if (matrix[i][j] == 0) dp[i][j][1] = dp[i + 1][j][1] + 1;
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
// ij可能出现的最大边长
let max = Math.min(dp[i][j][0], dp[i][j][1]);
for (let size = max; size >= 0; size--) {
// 如果i，j的最大边长为size，则更新
if (result[2] >= size) continue;
if (
dp[i + size - 1][j][0] >= size &&
dp[i][j + size - 1][1] >= size
) {
result = [i, j, size];
// 1,0 2,
}
}
}
}
}
return result[2] == 0 ? [] : result;
}
python3 解法, 执行用时: 188 ms, 内存消耗: 16.9 MB, 提交时间: 2023-04-22 11:35:52
'''
解题思路
1 阅读题目，比较容易想到的思路就是重构两个矩阵rMatrix和cMatrix(重构成一个矩阵可能更好理解)
对于rMatrix矩阵，rMatrix[row][col]表示从matrix[row][col]开始向右数有多少个0
对于cMatrix矩阵，cMatrix[row][col]表示从matrix[row][col]开始向下数有多少个0
2 重构矩阵后，剩下的就是遍历matrix矩阵
1）对于任意节点[row][col]，其能够组成的最大size是min(rMatrix[row][col], cMatrix[row][col])
2）对于任意节点[row][col]和size，能够组成方形的判断条件就是
cMatrix[row][col + size - 1]和rMatrix[row + size - 1][col]不小于size，即
组成方形的右上节点向下数至少有size个0
组成方形的左下节点向右数至少有size个0
'''
class Solution(object):
def calRMatrix(self, matrix, rMatrix):
for row in range(len(matrix) - 1, -1, -1):
count = 0
for col in range(len(matrix[0]) - 1, -1, -1):
if matrix[row][col] == 1:
count = 0
else:
count += 1
rMatrix[row][col] = count
return
def calCMatrix(self, matrix, cMatrix):
for col in range(len(matrix[0]) - 1, -1, -1):
count = 0
for row in range(len(matrix) - 1, -1, -1):
if matrix[row][col] == 1:
count = 0
else:
count += 1
cMatrix[row][col] = count
return
def checkSquareValid(self, rMatrix, cMatrix, row, col, size):
if row + size - 1 >= len(rMatrix) or col + size - 1 >= len(rMatrix[0]):
return False
rightUp = cMatrix[row][col + size - 1]
leftDonw = rMatrix[row + size - 1][col]
if rightUp >= size and leftDonw >= size:
return True
return False
def findSquare(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
rMatrix = [[0] * len(matrix[0]) for _ in range(len(matrix))]
cMatrix = [[0] * len(matrix[0]) for _ in range(len(matrix))]
resPos = [-1, -1]
resSize = 0
self.calRMatrix(matrix, rMatrix)
self.calCMatrix(matrix, cMatrix)
for row in range(len(matrix)):
for col in range(len(matrix[0])):
maxSize = min(rMatrix[row][col], cMatrix[row][col])
while maxSize > 0:
if self.checkSquareValid(rMatrix, cMatrix, row, col, maxSize):
break
maxSize -= 1
if maxSize > resSize:
resSize = maxSize
resPos = [row, col]
if resSize == 0:
return []
else:
return resPos + [resSize]
cpp 解法, 执行用时: 100 ms, 内存消耗: 37.1 MB, 提交时间: 2023-04-22 11:34:51
// 动态规划，cnt[r][c][0/1]表示以坐标r,c为起点向左/右最多的连续黑色块的数量
class Solution {
public:
vector<int> findSquare(vector<vector<int>>& matrix) {
vector<int> ans(3, 0);
int n = matrix.size();
if(n == 0) return {};
if(n == 1){
if(matrix[0][0] == 0)
return {0, 0, 1};
else
return {};
}
//cnt[r][c][0/1],0右侧,1下侧
vector<vector<vector<int>>> cnt(n, vector<vector<int>>(n, vector<int>(2)));
for(int r = n-1; r >= 0; r--){
for(int c = n-1; c >= 0; c--){
if(matrix[r][c] == 1)
cnt[r][c][0] = cnt[r][c][1] = 0;
else{
//统计cnt[r][c][0/1]
if(r < n-1) cnt[r][c][1] = cnt[r+1][c][1] + 1;
else cnt[r][c][1] = 1;
if(c < n-1) cnt[r][c][0] = cnt[r][c+1][0] + 1;
else cnt[r][c][0] = 1;
//更新当前最大子方阵
int len = min(cnt[r][c][0], cnt[r][c][1]);//最大的可能的边长
while(len >= ans[2]){//要答案r,c最小，所以带等号
if(cnt[r+len-1][c][0] >= len && cnt[r][c+len-1][1] >= len){
//可以构成长为len的方阵
ans = {r, c, len};
break;
}
len--;
}
}
}
}
return ans;
}
};