二维数组的动态规划——0/1矩阵、最大正方形
- 最大正方形
- 1277. 统计全为 1 的正方形子矩阵
- 221. 最大正方形
- 01矩阵
- 542. 01 矩阵
最大正方形
下面两个题目是非常相似的，只是一个统计正方形数目，一个统计最大正方形的面积。
1277. 统计全为 1 的正方形子矩阵
1277. 统计全为 1 的正方形子矩阵
给你一个
m * n的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
首先，如果矩阵matrix[i][j] = 1，那么就是一个大小为1的正方形。假设用二维数组dp进行统计，dp[i][j]即以matrix[i][j]为右下顶点的全是1组成的正方形的个数【其实也是以matrix[i][j]为右下点的全是由1组成的正方形的最大边长，最大正方形】。
我们从大小为1的正方形开始，要解决的问题是这个正方形如何扩大？根据官方题解中的图，很好理解，dp[i][j]与其上面、左边和左上三个角，且由其中最小的一个决定，即dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, matrix[i][j] +1
可以先处理第一列和第一行，只要matrix[i][j]为1，dp[i][j]就等于1，同时统计的正方形子矩阵数量+1。完整java代码如下：
class Solution {
public int countSquares(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int[][] count = new int[rows][cols];
int sum = 0;
//单独处理
for(int i = 0; i < cols; i++){
count[0][i] = matrix[0][i];
sum += count[0][i];
}
//单独处理第一列
for(int i =1; i< rows; i++){
count[i][0] = matrix[i][0];
sum += count[i][0];
}
for(int i = 1; i < rows; i++)
for(int j = 1; j < cols; j++){
if(matrix[i][j] == 0)
count[i][j] = 0;
else
count[i][j] = minSan(count[i-1][j-1], count[i-1][j] , count[i][j-1]) + 1;
sum += count[i][j];
}
return sum;
}
//单独写了一个函数判断三者中的最小值
//实际用min(a,min(b,c))是一样的
public int minSan(int a, int b ,int c){
int minCur;
if(a < b)
minCur = a;
else
minCur = b;
if(minCur> c)
minCur = c;
return minCur;
}
}
221. 最大正方形
221. 最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
这个题目和上面是类似的，上面的dp[i][j]是以matrix[i][j]为右下角的，全部由1组成的正方形的数量，其实也就是以matrix[i][j]为右下角的正方形的最大边长。只是这个题目找的是dp[i][j]中的最大值。 需要注意的是，这个题目中matrix[i][j]是char类型的，是’0’'1’字符而不是数字。
完整java代码如下：
class Solution {
public int maximalSquare(char[][] matrix) {
int ansMax = 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] count = new int[rows][cols];
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
//第一行和第一列，特殊情况
if( i == 0 || j == 0)
//'0'的ASCII码对应48
count[i][j] = matrix[i][j] - 48;
else if(matrix[i][j] == '0')
count[i][j] = 0;
else
count[i][j] = Math.min(Math.min(count[i-1][j-1],count[i-1][j]),count[i][j-1]) + 1;
//更新dp[i][j]的同时，更新ansMax，记录最大的正方形面积
ansMax = ansMax > count[i][j] ? ansMax : count[i][j];
}
}
//返回的是面积
return ansMax*ansMax;
}
}
01矩阵
542. 01 矩阵
542. 01 矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
理解题意，是要我们找mat[i][j]离其周围的最近的0的距离，这里的周围是四个方向，上边[i-1][j]、下边[i+1][j]、左边[i][j-1]、右边[i][j+1]。如果用dp[i][j]记录这个最近距离，相当于dp[i][j] = min( dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + 1。
这个题要结果的问题是如何更新这个dp？遍历（逐个更新其元素）一个二维数组需要两成循环，横纵坐标能够表示两个遍历方向，我们需要四个，那么进行两次遍历更新，一个往左下，一个往右上【当然这里选择右下和左上的方向一样的】。代码如下：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int[][] distance = new int[rows][cols];
for (int i = 0; i < rows; ++i) {
// 因为后续是求dp[i][j]的最小情况，先赋一个较大值
Arrays.fill(distance[i], rows + cols + 1);
}
//如果mat[i][j] = 0，那么dp[i][j]自然也等于0
for(int i = 0; i < rows; i++)
for(int j = 0; j < cols; j++){
if(mat[i][j] == 0)
distance[i][j] =0;
}
//往左下的方向更新dp
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(i > 0)
distance[i][j] = Math.min(distance[i][j], distance[i-1][j] + 1);
if(j > 0)
distance[i][j] = Math.min(distance[i][j], distance[i][j-1] + 1);
}
}
//往右上的方向更新dp
for(int i = rows - 1; i >= 0; i--){
for(int j = cols - 1; j >= 0; j--){
if(i < rows - 1)
distance[i][j] = Math.min(distance[i][j], distance[i+1][j] +1 );
if(j < cols - 1)
distance[i][j] = Math.min(distance[i][j], distance[i][j+1] + 1);
}
}
return distance;
}
}
