题目

image.png

思路

  • 思路一：暴力递归
  • 思路二：备忘录
  • 思路三：动态规划
  • 思路四：优化dp数组动态规划
  • 动态规划：dp[i][j]表示dp[i][j]包含在内所能表示的最大正方形边长，通过观察我们可以得知dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], Math.min(dp[i - 1][j - 1])

代码

  1.     //1.暴力递归
  2.     int max = 0;
  3.     public int maximalSquare(char[][] matrix) {
  4.         recur(matrix, matrix.length - 1, matrix[0].length - 1);
  5.         return max * max;
  6.     }
  8.     public int recur(char[][] matrix, int i, int j) {
  9.         if (i < 0 || j < 0) return 0;
  10.         int val = matrix[i][j] - '0';
  11.         int res =  Math.min(
  12.             Math.min(recur(matrix, i - 1, j), recur(matrix, i, j - 1)), 
  13.             recur(matrix, i - 1, j - 1)) + val;
  14.         max = Math.max(res, max);
  15.         return val == 0 ? 0 : res;
  16.     }
  18.     //2.备忘录
  19.     int max = 0;
  20.     int[][] dp;
  21.     public int maximalSquare(char[][] matrix) {
  22.         dp = new int[matrix.length][matrix[0].length];
  23.         for (int i = 0; i < matrix.length; i++) {
  24.             for (int j = 0; j < matrix[0].length; j++) {
  25.                 dp[i][j] = -1;
  26.             }
  27.         }
  28.         recur(matrix, matrix.length - 1, matrix[0].length - 1);
  29.         return max * max;
  30.     }
  32.     public int recur(char[][] matrix, int i, int j) {
  33.         if (i < 0 || j < 0) return 0;
  34.         if (dp[i][j] != -1) return dp[i][j];
  35.         int val = matrix[i][j] - '0';
  36.         int res =  Math.min(
  37.             Math.min(recur(matrix, i - 1, j), recur(matrix, i, j - 1)), 
  38.             recur(matrix, i - 1, j - 1)) + val;
  39.         max = Math.max(res, max);
  40.         dp[i][j] = val == 0 ? 0 : res;
  41.         return dp[i][j];
  42.     }
  44.     //3.动态规划
  45.     public int maximalSquare(char[][] matrix) {
  46.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  47.         int res = 0;
  48.         int[][] dp = new int[matrix.length][matrix[0].length];
  49.         for (int i = 0; i < matrix.length; i++) {
  50.             dp[i][0] = matrix[i][0] - '0';
  51.             res = Math.max(res, dp[i][0]);
  52.         }
  53.         for (int j = 0; j < matrix[0].length; j++) {
  54.             dp[0][j] = matrix[0][j] - '0';
  55.             res = Math.max(res, dp[0][j]);
  56.         }
  57.         for (int i = 1; i < matrix.length; i++) {
  58.             for (int j = 1; j < matrix[0].length; j++) {
  59.                 dp[i][j] = matrix[i][j] - '0';
  60.                 if (dp[i][j] == 1) {
  61.                     dp[i][j] = Math.min(
  62.                         Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  63.                     res = Math.max(res, dp[i][j]);
  64.                 }
  65.             }
  66.         }
  67.         return res * res;
  68.     }
  70.     //后面觉得不用开辟数组，效率会高一点，结果一样是7ms，反而花费空间更多
  71.     public int maximalSquare(char[][] matrix) {
  72.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  73.         char res = '0';
  74.         for (int i = 0; i < matrix.length; i++) {
  75.             for (int j = 0; j < matrix[0].length; j++) {
  76.                 if (i > 0 && j > 0 && matrix[i][j] == '1') {
  77.                     matrix[i][j] = (char)
  78.                     (min(min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]) + 1);
  79.                 }
  80.                 res = max(res, matrix[i][j]);
  81.             }
  82.         }
  83.         return (res - '0') * (res - '0');
  84.     }
  86.     public char min(char c1, char c2) {
  87.         if (c1 < c2) return c1;
  88.         return c2;
  89.     }
  91.     public char max(char c1, char c2) {
  92.         if (c1 > c2) return c1;
  93.         return c2;
  94.     }
  97.      //后面觉得直接把初始化条件放在里面去，好一点，7ms
  98.      public int maximalSquare(char[][] matrix) {
  99.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  100.         int res = 0;
  101.         int[][] dp = new int[matrix.length][matrix[0].length];
  102.         for (int i = 0; i < matrix.length; i++) {
  103.             for (int j = 0; j < matrix[0].length; j++) {
  104.                 dp[i][j] = matrix[i][j] - '0';
  105.                 if (i > 0 && j > 0 && dp[i][j] == 1) {
  106.                     dp[i][j] = Math.min(
  107.                         Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  108.                 }
  109.                 res = Math.max(res, dp[i][j]);
  110.             }
  111.         }
  112.         return res * res;
  113.     }
  115.     //再下一步就是优化dp数组，由于只用到三个元素可以压缩为一维，6ms
  116.     public int maximalSquare(char[][] matrix) {
  117.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  118.         int res = 0, prev = 0, len = matrix[0].length;;
  119.         int[] dp = new int[len];
  120.         for (int i = 0; i < matrix.length; i++) {
  121.             for (int j = 0; j < matrix[0].length; j++) {
  122.                 int t = dp[j];
  123.                 dp[j] = matrix[i][j] - '0';
  124.                 if (i > 0 && j > 0 && dp[j] == 1) {
  125.                     dp[j] = Math.min(Math.min(t, dp[j - 1]), prev) + 1;
  126.                 }
  127.                 prev = t;
  128.                 res = Math.max(dp[j], res);
  129.             }
  130.         }
  131.         return res * res;
  132.     }
  134.     //后来看到别人写的更好初始值处理的动态规划，7ms
  135.     public int maximalSquare(char[][] matrix) {
  136.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  137.         int res = 0, m = matrix.length, n = matrix[0].length;
  138.         int[][] dp = new int[m + 1][n + 1];
  139.         for (int i = 1; i <= m; i++) {
  140.             for (int j = 1; j <= n; j++) {
  141.                 if (matrix[i - 1][j - 1] == '1') {
  142.                     dp[i][j] = Math.min(
  143.                         Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  144.                     res = Math.max(res, dp[i][j]);
  145.                 }
  146.             }
  147.         }
  148.         return res * res;
  149.     }
  151.     //我再把它压缩为一维数组，5ms
  152.      public int maximalSquare(char[][] matrix) {
  153.         if (matrix.length == 0 || matrix[0].length == 0) return 0;
  154.         int res = 0, prev = 0, len = matrix[0].length;;
  155.         int[] dp = new int[len + 1];
  156.         for (int i = 1; i <= matrix.length; i++) {
  157.             for (int j = 1; j <= matrix[0].length; j++) {
  158.                 int t = dp[j];
  159.                 if (matrix[i - 1][j - 1] == '1') {
  160.                     dp[j] = Math.min(Math.min(t, dp[j - 1]), prev) + 1;
  161.                     res = Math.max(dp[j], res);
  162.                 } else {
  163.                     dp[j] = 0;
  164.                 }
  166.                 prev = t;
  167.             }
  168.         }
  169.         return res * res;
  170.     }

最大正方形