在一个二维01矩阵中找到全为1的最大正方形
样例
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
返回 4
动态规划的办法,我们可以先求出正方形最大的边长,我们推导出的公式是,原来的数组是arr[][];
f[][]是存储结果的表,当最大正方形包括arr[i][j]的时候,f[i][j] = min(f[i-1][j-1],f[i][j-1],f[i-1][j])+1;当不包含f[i][j]的时候,f[i][j] =0;此时 最大的边长为num = max(f[i][j],num)
f[][]是存储结果的表,当最大正方形包括arr[i][j]的时候,f[i][j] = min(f[i-1][j-1],f[i][j-1],f[i-1][j])+1;当不包含f[i][j]的时候,f[i][j] =0;此时 最大的边长为num = max(f[i][j],num)
完整代码如下:
package lintcode; import java.util.Scanner; /** * Created by Taoyongpan on 2017/11/15. * 436,在一个二维01矩阵中找到全为1的最大正方形 * 动态规划的思想 * 求出正方形最长的边长 */ public class MaxSquare { public static int SquareMax(int[][] arr){ int n = arr.length; int m = arr[0].length; int num = 0; int[][] f = new int[n+1][m+1]; if (n<=0||m<=0){ return num*num; } //初始化f数组 for (int i = 0;i<n;i++){ f[i][0] = arr[i][0]; num = Math.max(f[i][0],num); } for (int j = 0; j<m;j++){ f[0][j] = arr[0][j]; num = Math.max(f[0][j],num); } for (int i = 1;i<n;i++){ for (int j = 1;j<m;j++){ if (arr[i][j]==1) f[i][j] = Math.min(Math.min(f[i-1][j-1],f[i][j-1]),f[i-1][j])+1; else f[i][j] = 0; num = Math.max(f[i][j],num); } } return num*num; } //主函数 public static void main(String[] args){ Scanner sc = new Scanner(System.in); while (sc.hasNext()){ int n = sc.nextInt(); int m = sc.nextInt(); int[][] arr = new int[n+1][m+1]; for (int i = 0 ;i<n;i++){ for (int j = 0;j<m;j++){ arr[i][j] = sc.nextInt(); } } System.out.println(SquareMax(arr)); } } }
相关推荐
华为机考编程题目当中一道经典的题目,矩阵由01组成,求包含1的最大正方形,这里用的是动态规划求解,思路有点抽象,代码很简单,编程语言java.
最大正方形.md
php_leetcode题解之最大正方形
最大正方形(洛谷-P1387).rar
python python_leetcode面试题解之第221题最大正方形_题解
javascript javascript_leetcode面试题解动态规划问题之第221题最大正方形_题解
n 编号并按照顺 序围成一圈,从第 k 个猴子起,由1开始报数,报到m时,该猴子就跳出圈外,下一只猴子再次由1开始报数,如此循环,直到圈内剩下一只猴子时,这只猴
Inscribed_Rectangle 包提供 2 个低级计算机视觉/图像分析功能,能够定位内接在由二进制掩码(黑白图像)定义的任意形状内的最大正方形或矩形。 仅考虑具有垂直/水平边缘的矩形。 已证明的函数可用作解决更大图像...
for (const [len, width] of rectangles) {for (const [len, width] of rectangles) {
在舞台正中央绘制一个边长为200的正方形,要求: 1、围绕舞台中心绘制正多边形,均匀分布在四个象限中 2、正方形边长为200个单位,线条粗细、颜色自定 3、利用画笔绘制正方形,不能有多余的线条
* 圆内最大正方形的面积计算:圆内最大正方形的面积可以根据圆的半径计算,公式为A=s²,其中A为圆内最大正方形的面积,s为正方形的边长。 四、圆的分割和组合 * 圆的分割:圆可以分割成多个扇形或扇形组成的图形...
编写程序,输出n层正方形图案。正方形图案最外层是第一层,每层用的数字和层数相同。例如,输入3那么输出为:1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1
华为机考编程题目当中一道经典的题目,矩阵由01组成,求包含1的最大正方形,这里用的是逻辑推理求解,编程语言java.
1020 最大正方形 这题和1017很相似,不过有更快的解决方法 1021 背包问题 1022 Longest Common Sequence 也可用二叉搜索树(nlog时间)解决,见llj的书 1023 Happy Travel 转化为背包问题 1029 交点问题 据说有一个...
可以计算出最大正方形 E 的面积。 19.本题考查了几何体的形状。在 OC 平分∠AOB,点 P 是 OC 上一点,PM⊥OB 于点 M,点 N 是射线 OA 上的一个动点,可以计算出∠AOC。 本资源涵盖了初二数学的多个方面,包括数论...
13 2 网格中的最大正方形 157 13 3 直方图中的最大长方形 158 13 4 网格中的最大长方形 159 13 5 合并长方形 160 13 6 不相交长方形的合并 164 第 14 章 计算 165 14 1 最大公约数 165 14 2 贝祖等式 165 14 3 二项...
例如:在右图中,外圈最大正方形的边长为8厘米,那么最中间的小正方形的面积是 __________平方厘米。 16. 竞赛:竞赛的数学应用。 例如:一次数学竞赛,共有50人参加,其中第一题做错的有18人,第二题做错的有21人...
5. 用一根长 20 米的铁丝围成一个最大的正方形,这个正方形的面积是 25 平方米。C、25 平方米 这个题目考查学生对正方形的定义和面积计算的理解。 五、画图题 画一个长方形和一个正方形,他们的面积都是 12 平方...
定位作物开口目标是将图像裁剪为适合设备纵横比的最大正方形。 阴影视图(“阻挡器”)出现在要裁剪的区域上。 图像在阴影视图下方来回滑动。 用户点击“裁剪”按钮将图像裁剪为方形区域。 自动布局“计算”方形裁剪...