怎么做网站的浏览量统计,做外贸的数据网站,网站项目设计,网站开发开题报告范文2019用dp计算矩形面积 文章目录1题目理解2分析2.1 暴力搜索2.2 动态规划3 相关题目1题目理解
输入#xff1a;char[][] matrix 是一个二维数组#xff0c;值由0和1组成。 输出#xff1a;一个矩形的面积#xff0c;这个矩形只包含1。 例子#xff1a; Input: [ [“1”,“0”,…用dp计算矩形面积
文章目录1题目理解2分析2.1 暴力搜索2.2 动态规划3 相关题目1题目理解
输入char[][] matrix 是一个二维数组值由0和1组成。 输出一个矩形的面积这个矩形只包含1。 例子 Input: [ [“1”,“0”,“1”,“0”,“0”], [“1”,“0”,“1”,“1”,“1”], [“1”,“1”,“1”,“1”,“1”], [“1”,“0”,“0”,“1”,“0”] ] Output: 6
2分析
最开始没理解直接想之前做过从一个点向4个方向延伸找最大值。写完发现图形不是矩形。 开始思考因为是矩形该怎么做。思路参考力扣。
2.1 暴力搜索
枚举左上角(x1,y1)坐标和右下角(x2,y2)左边计算面积。时间复杂度O(m3n3)O(m^3n^3)O(m3n3)。
2.2 动态规划
dp[i][j] 在第i行以j结尾的最长的包含1的子数组的长度。 dp[i][j]0,matrix[i][j]′0′dp[i][j] 0,matrix[i][j]0dp[i][j]0,matrix[i][j]′0′ dp[i][j]dp[i][j−1]1,matrix[i][j]′1′dp[i][j] dp[i][j-1]1,matrix[i][j]1dp[i][j]dp[i][j−1]1,matrix[i][j]′1′
例如上面的例子 dp[1] {1,0,1,2,3} 知道了每一行的宽度从第i行开始向上计算找到最小的宽度乘以高就是矩形的面积。 这是一个动态规划dp的值只是返回值一部分的例子。
class Solution {private int maxSum;public int maximalRectangle(char[][] matrix) {if(matrixnull || matrix.length0) return 0;int m matrix.length;int n matrix[0].length;int maxArea 0;int[][] dp new int[m][n];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]1){dp[i][j] (j0?1:dp[i][j-1]1);int minWidth dp[i][j];for(int upRow i;upRow0;upRow--){int height i-upRow1;minWidth Math.min(minWidth,dp[upRow][j]);maxArea Math.max(maxArea,minWidth*height);}}}}return maxArea;}}3 相关题目
304 Range Sum Query 2D – Immutable 计算一个矩阵范围内的数字和
class NumMatrix {int[][] dp;public NumMatrix(int[][] matrix) {if(matrix null || matrix.length 0) return;int m matrix.length;int n matrix[0].length;dp new int[m][n];for(int i0;im;i){for(int j 0;j n;j){dp[i][j] (i0?dp[i-1][j]:0) (j0?dp[i][j-1]:0) - (i0 j0? dp[i-1][j-1]:0) matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {if(dp null) return 0;return dp[row2][col2] - (row10?dp[row1-1][col2]:0) - (col1 0 ?dp[row2][col1-1]:0) (row10 col10 ?dp[row1-1][col1-1]:0);}
}221 Maximal Square 计算正方形的最大面积
class Solution {public int maximalSquare(char[][] matrix) {if(matrixnull || matrix.length0) return 0;int m matrix.length;int n matrix[0].length;int maxSide 0;int[][] dp new int[m][n];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]1){if(i0 || j0){dp[i][j] 1;}else{dp[i][j] Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))1;}maxSide Math.max(maxSide,dp[i][j]);}}}return maxSide * maxSide;}
}1277 Count Square Submatrices with All Ones 数一数正方形的个数
class Solution {public int countSquares(int[][] matrix) {int count 0;int m matrix.length;int n matrix[0].length;int[][] dp new int[m][n];for(int i 0;im;i){for(int j0;jn;j){if(matrix[i][j] 1){if(i0 || j0){dp[i][j] 1;}else{dp[i][j] Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])1;}count dp[i][j];}}}return count;}}
