软件测试工程师 namespace Transformer oracle shell cordova sockets delphi angularjs版本 后台管理模板下载 bootstrap后台管理模板 ios视频教程 web前端开发实战项目 easyui视频 ps视频教程全集完整版 css鼠标悬浮样式 mysql时间戳转时间 python数据 python中str函数 java实现 java基础数据类型 如何查看java版本 java数组追加 java时间格式化 java多线程处理 java异常 java判断 一键刷入recovery hadoop权威指南 俄罗斯方块c语言代码 bash命令 飞猪ip 8元秒电脑 烧饼修改器打不开 上传附件 挑战程序设计竞赛 关闭页面 文件粉碎工具 计算机科学概论 模拟邻居
当前位置: 首页 > 学习教程  > 编程语言

lc 221. 最大正方形

2020/10/8 20:14:38 文章标签:

本题我也能很快的想到用dp,dp[i][j]表示以[i,j]为右下角的最大正方形的边长 但是在递推的时候,没有想到直接利用之前的计算的办法,当时想的是除了dp[i-1][j-1],就是看(i,j)左边和上边为1的个数 但是实际上可以利用dp[i-1][j],dp…

本题我也能很快的想到用dp,dp[i][j]表示以[i,j]为右下角的最大正方形的边长

但是在递推的时候,没有想到直接利用之前的计算的办法,当时想的是除了dp[i-1][j-1],就是看(i,j)左边和上边为1的个数

但是实际上可以利用dp[i-1][j],dp[i][j-1]

参考:

https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

class Solution {
    // dp[i][j]表示以[i,j]为右下角的最大正方形的面积
    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int[][] dp=new int[matrix.length][matrix[0].length];
        int max=0;
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                if(i==0||j==0){
                    dp[i][j]=matrix[i][j]=='1'?1:0;
                }else{
                    if(matrix[i][j]!='1'){
                        dp[i][j]=0;
                    }else
                        dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                }
                max=Math.max(max,dp[i][j]);
            }
        }
        return max*max;
    }
}

 


本文链接: http://www.dtmao.cc/news_show_250230.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?