LeetCode Maximal Square
2024-10-18 00:30:02
原题链接在这里:https://leetcode.com/problems/maximal-square/
题目:
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
题解:
DP, 状态: 以当前点为右下角的最大都包含1的square边长.
转移方程 如果当前点为1, dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1.
初始化dp[m+1][n+1], 多一行一列方便处理边界.
res 一直取maintain dp的最大值.
优化dp成一行, 因为只需要左, 上, 和左斜上三个值. prev 来保存左斜上.
Time Complexity: O(m*n). m = matrix.length, n = matrix[0].length.
Space: O(n).
AC Java:
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
} int res = 0;
int m = matrix.length;
int n = matrix[0].length;
int [] dp = new int[n+1];
int prev = 0; for(int i = 1; i<=m; i++){
for(int j = 1; j<=n; j++){
int temp = dp[j];
if(matrix[i-1][j-1] == '1'){
dp[j] = Math.min(Math.min(dp[j], dp[j-1]), prev) + 1;
}else{
dp[j] = 0;
}
prev = temp;
res = Math.max(res, dp[j]);
}
}
return res*res;
}
}
最新文章
- UI-切圆角、透明度、取消按钮点击高亮效果、按钮文字带下划线
- hibernate延迟加载
- linux基础命令学习(一)
- 实现IHttpModule接口,给每个页面输出一段脚本
- 关于Javascript的内存泄漏问题的整理稿
- 【原】GO 语言常见错误
- 解决“无法连接到Python代码运行助手。请检查本机的设置”问题
- MySQL show binglog event in &#39;log_name&#39;
- 在WINDOWS下 三步快速配置 eclipse c++ 环境
- 关于用node批量修改文件名
- Linux系列教程(八)——Linux常用命令之压缩和解压缩命令
- AssertionError while merging cells with xlwt (Python)
- 面试(三)---volatile
- 解决time_wait过多
- 用户名、密码等15个常用的js正则表达式
- express.Router
- 使用postman做接口测试(一)
- ZT 感触的屌丝职场记 投递人 itwriter 发布于 2013-05-27 09:21 评论(18) 有3402人阅读 原文链接 [收藏] &#171; &#187; 作者@幻想哥呀幻想哥 有一位屌丝男,从小抱着报效祖国的理想上了大学,毕业后干了 IT 行业,高中那时候看文汇报说,搞 IT 的在上
- Ajax请求数据与删除数据后刷新页面
- div+css 制作表格
热门文章
- libtiff 生成48位色tif图片
- linux下安装uuid库
- 利用Oracle的row_number() over函数消除重复的记录
- VTKMY 3.3 VS 2010 Configuration 配置
- html5文章 -- 应用HTML5 开发手机APP
- kail-linux 下载地址
- HDU 4825 Xor Sum(经典01字典树+贪心)
- Java SSH库使用简介:Apache sshd和JSch(Java Secure Channel)
- Ubuntu 安装 ImageMagic(6.9.1-6)及 PHP 的 imagick (3.0.1)扩展
- Solr高亮详解