首页 / JAVA / Java for LeetCode 221 Maximal Square

Java for LeetCode 221 Maximal Square

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java for LeetCode 221 Maximal Square，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含995字，纯文字阅读大概需要2分钟。

内容图文

Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing all 1‘s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 11 1
1 1 11 1
1 0 0 1 0

Return 4.

解题思路：

dp问题，用一个dp[i][j]保存matrix[i][j]作为右下节点的时候的最大矩形的边长，JAVA实现如下：

    public int maximalSquare(char[][] matrix) {
		if (matrix.length == 0 || matrix[0].length == 0)
			return 0;
		int res = 0;
		int[] dp = new int[matrix[0].length];
		for (int i = 0; i < matrix[0].length; i++)
			if (matrix[0][i] == ‘1‘){
				dp[i] = 1;
			    res=1;
			}
		for (int i = 1; i < matrix.length; i++) {
			dp[0] = matrix[i][0] == ‘1‘ ? 1 : 0;
			res=Math.max(res, dp[0]);
			for (int j = 1; j < matrix[0].length; j++) {
				if(matrix[i][j]==‘0‘)
					dp[j]=0;
				else if (dp[j] == dp[j - 1]
						&& matrix[i - dp[j]][j - dp[j]] == ‘0‘) {
					dp[j] = Math.min(dp[j], dp[j - 1]);
				} else
					dp[j] = Math.min(dp[j], dp[j - 1]) + 1;
				res=Math.max(res, dp[j]);
			}
		}
		return res*res;
    }

 

原文：http://www.cnblogs.com/tonyluis/p/4578743.html

内容总结

以上是互联网集市为您收集整理的Java for LeetCode 221 Maximal Square全部内容，希望文章能够帮你解决Java for LeetCode 221 Maximal Square所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1225807.html

来源：【匿名】