题解 | JAVA #最大正方形# [P0-T2]

最大正方形

http://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e

mem[i][j]: 右下角坐标为(i,j)分正方形最大边长

if matrix[i][j] = 1: 
  mem[i][j] = 1+ MIN{
     mem[i-1][j], 
     mem[i-1][j-1], 
     mem[i][j-1]
  }
import java.util.*;

public class Solution {
    public int solve (char[][] matrix) {
      if (matrix.length == 0 || matrix[0].length == 0) return 0;
      
      // 把char换成int. 题目给char是真的烦
      int[][] mem = new int[matrix.length][matrix[0].length];
      for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
          mem[i][j] = (matrix[i][j] == '1') ? 1 : 0;
        }
      }
      
      int maxW = 0;
      // mem[0][j] and mem[i][0]都等于matrix[i][j], 不用再算
      for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[0].length; j++) {
          if (mem[i][j] == 0) {
            continue;
          }
          mem[i][j] = 1 + Math.min(mem[i-1][j], 
                                   Math.min(mem[i][j-1], mem[i-1][j-1]));
          maxW = Math.max(maxW, mem[i][j]);
        }
      }
      
      return maxW * maxW;
    }
}
全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务