• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

最大正方形 暴力+动态规划

admin

11月 28, 2021

题目:

  

 思路:

  1 暴力 : 从每一个单元格出发 每次在下方 右方 新作一行一列进行判断是否满足条件

  2 动态规划 :  

    dp[i][j]由其上方、左方和左上方的三个相邻位置的dp值决定

    当前位置的元素值等于三个相邻位置的元素中的最小值加 1

    根据题目分析状态转移方程:

    dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1


(一)代码  暴力

class Solution {

    public int maxSide = 0;

    public int maximalSquare(char[][] matrix) {

        //最大正方形,遍历每一个单元格,从每一个单元格 向下 向上 斜向下
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ; j++){
                if(matrix[i][j] == '1'){
                    getMaxNum(i,j,matrix);
                }
            }
        }
        return maxSide * maxSide;
    }

    public void getMaxNum(int x, int y , char[][] matrix){

        // 遇到一个 1 作为正方形的左上角
        maxSide = Math.max(maxSide, 1);
        // 计算可能的最大正方形边长
        int currentMaxSide = Math.min(matrix.length - x, matrix[0].length - y);
        for (int k = 1; k < currentMaxSide; k++) {
            // 判断新增的一行一列是否均为 1
            boolean flag = true;
            if (matrix[x + k][y + k] == '0') {
                break;
            }
//这块 important 注意复习 for (int m = 0; m < k; m++) { if (matrix[x + k][y + m] == '0' || matrix[x + m][y + k] == '0') { flag = false; break; } }
       
if (flag) { maxSide = Math.max(maxSide, k + 1); } else { break; } } } }

(二)动态规划  还是用算法  写起来爽   慢慢练吧 

class Solution {

    public int maximalSquare(char[][] matrix) {

        int max = 0;
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return max;
        }
        //动态规划
        //分析状态转移方程为 dp[i][j] = min(dp[i-1][j-1],dp[i-1][j] + d[i][j-1]) + 1
        //注意在for中初始化dp[i][j] 含有0的下标 内容为1
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ;j++){
                if(matrix[i][j] == '1'){
                    //最左上方的 i ==0 || j == 0 初始化为1
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                    }
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max * max;
    }
}

        路在何方

发表回复

您的电子邮箱地址不会被公开。