LeetCode 221. 最大正方形
2020-05-08 16:07:52来源:博客园 阅读 ()
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'的位置,由此位置开始BFS,每成功扩展一次BFS边长+1;
- 记录所有位置为'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}} \]
步骤:
- 对于0行和0列,只记录是否有'1'即可;
- 从[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 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash