首页 > 编程语言 > 详细

[LeetCode][JavaScript]Maximal Square

时间:2016-02-28 22:48:18      阅读:331      评论:0      收藏:0      [点我收藏+]

Maximal Square

Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing all 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.
 
 
 

 
 
 
找出地图中最大的一个由1组成的正方形。
 
动态规划,大的正方型是由小的正方形加上两条边组成的。
按照正常的顺序遍历二维数组,第一次遇到1的时候,dp数组的对应位置也记做1.
再遇到1的时候,查看这个点的左上角(dp[i - 1][j - 1])是不是存在,以及检查上边和左边是否全部是1。
 
举例来说:
1 1
1 1
遍历到右下的点(坐标[1][1])。
如果左上角是1,查看当前点的左边和上面是不是也是1,如果是,则说明构成了2X2的正方形,把当前点在dp数组中记做2。
 
复杂点的情况比如:
1 1 0
1 1 1
1 1 1
坐标为[0][0]的点在dp中记做1,没有问题。
坐标为[1][1]的点记做2,但遍历到[3][3]的时候,因为[0][2]是0,所以[3][3]在dp中只能记做2。
 
最后,因为dp中记录的是矩形的宽度,return的时候返回平方数。
 
 1 /**
 2  * @param {character[][]} matrix
 3  * @return {number}
 4  */
 5 var maximalSquare = function(matrix) {
 6     if(matrix.length === 0) return 0;
 7     var max = 0, i, j, dp = [], tmp,
 8         height = matrix.length, width = matrix[0].length;
 9     for(i = 0; i < height; i++)
10         dp[i] = [];
11     for(i = 0; i < height; i++){
12         for(j = 0; j < width; j++){
13             if(matrix[i][j] === ‘1‘){
14                 tmp = getSquare(i, j);
15                 dp[i][j] = tmp;
16                 max = Math.max(max, dp[i][j]);
17             }
18         }
19     }
20     return max * max;
21 
22     function getSquare(i, j){
23         if(!matrix[i - 1] || !matrix[i - 1][j - 1])
24             return 1;
25         var index, width = dp[i - 1][j - 1];
26         if(!width) return 1;
27         for(index = 1; index <= width; index++)
28             if(!matrix[i - index] || matrix[i - index][j] !== ‘1‘
29                 || matrix[i][j - index] !== ‘1‘)
30                 return index;
31         return width + 1;
32     }
33 };

 

[LeetCode][JavaScript]Maximal Square

原文:http://www.cnblogs.com/Liok3187/p/5225665.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!