LeetCode 221. 最大正方形

2020-05-08 16:07:52来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LeetCode 221. 最大正方形

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 221. 最大正方形

题目

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

本题可用BFS/广度优先搜索或者dp动态规划解决;

思路1-BFS

思路解析:对于matrix[i][j]为'1'的位置,若其matrix[i+1][j]、matrix[i][j+1]、matrix[i+1][j+1]也都为'1',那么由matrix[i][j]可以得到一个边长为2的正方形;
按照整个逻辑递归BFS即可尝试扩大正方形的边长;

  1. 遍历找到'1'的位置,由此位置开始BFS,每成功扩展一次BFS边长+1;
  2. 记录所有位置为'1'的BFS最大值即最大面积;

算法复杂度: m、n分别为matrix的行和列

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(mn * min(m,n)^{2}\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(mn\right)}} $

思路2-dp动态规划

思路解析:与思路1相似,但是dp是把matrix[i][j]为'1'位置的左边、上边和左上位置的数据亚索至[i][j]位置;
对于matrix[i][j]为'1'的位置能得到的最大正方形的边长为dp[i][j]:

\[{\color{Magenta}{dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1}} \]

步骤:

  1. 对于0行和0列,只记录是否有'1'即可;
  2. 从[1][1]位置开始dp,并每次记录所得到的最大边长,dp完成后由得到的最大边长计算面积即可;

算法复杂度: m、n分别为matrix的行和列

  • 时间复杂度: $ {\color{Magenta}{\Omicron\left(nm\right)}} $
  • 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

package leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ZhouJie
 * @date 2020年5月8日 下午5:06:45 
 * @Description: 221. 最大正方形
 *
 */
public class LeetCode_0221 {

}

class Solution_0221 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月8日 下午6:49:30 
	 * @param: @param matrix
	 * @param: @return
	 * @return: int
	 * @Description: 1-BFS;
	 *
	 */
	public int maximalSquare_1(char[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return 0;
		}
		int row = matrix.length;
		int col = matrix[0].length;
		Deque<Integer> deque = new ArrayDeque<Integer>();
		int size = 0, maxS = 0;
		// 右方、下方、右下方的方位
		int[] dx = new int[] { 1, 0, 1 };
		int[] dy = new int[] { 0, 1, 1 };
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				// 若当前是1则开始BFS
				if (matrix[i][j] == '1') {
					deque.clear();
					// 保存坐标,不使用数组,利用int整除和取模的特性存储坐标信息
					deque.offer(i * col + j);
					// 初始变长为1
					int a = 1;
					boolean f = false;
					while (!deque.isEmpty()) {
						maxS = Math.max(a * a, maxS);
						size = deque.size();
						while (size-- > 0) {
							Integer p = deque.poll();
							int x = p / col;
							int y = p % col;
							int x0, y0;
							for (int k = 0; k < 3; k++) {
								x0 = x + dx[k];
								y0 = y + dy[k];
								// 当前位置的右方、下方、和右下方的位置也必须都是1才能扩大正方形的边长,否则BFS到此为止
								if (x0 < row && y0 < col && matrix[x0][y0] == '1') {
									deque.offer(x0 * col + y0);
								} else {
									f = true;
									break;
								}
							}
						}
						if (f) {
							break;
						}
						a++;
					}
				}
			}
		}
		return maxS;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月8日 下午6:49:40 
	 * @param: @param matrix
	 * @param: @return
	 * @return: int
	 * @Description: 2-dp动态规划;
	 *
	 */
	public int maximalSquare_2(char[][] matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return 0;
		}
		int row = matrix.length;
		int col = matrix[0].length;
		// 记录最大边长
		char max = '0';
		// dp逻辑,第0行和第0列只需要记录是否有1,从[1][1]开始dp,对于之后的[i][j]逻辑为:
		// 若[i][j]不为0,则:
		// dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1,dp[i][j]
		// dp[i][j]可能为最大边长,因为matrix本身就是dp所需的初始状态,只是保存的为char类型,需要转int类型,所以可以直接用matrix进行dp
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if ((i == 0 || j == 0)) {
					if (max == '0' && matrix[i][j] == '1') {
						max = '1';
					}
				} else if (matrix[i][j] > '0') {
					matrix[i][j] = matrix[i][j - 1] < matrix[i - 1][j] ? matrix[i][j - 1] : matrix[i - 1][j];
					matrix[i][j] = matrix[i][j] < matrix[i - 1][j - 1] ? matrix[i][j] : matrix[i - 1][j - 1];
					matrix[i][j]++;
					max = max > matrix[i][j] ? max : matrix[i][j];
				}
			}
		}
		return (max - '0') * (max - '0');
	}
}


原文链接:https://www.cnblogs.com/izhoujie/p/12852600.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:LeetCode 297. 二叉树的序列化与反序列化

下一篇:LeetCode 面试题37. 序列化二叉树