专栏首页Michael阿明学习之路程序员面试金典 - 面试题 17.23. 最大黑方阵(DP)

程序员面试金典 - 面试题 17.23. 最大黑方阵(DP)

1. 题目

给定一个方阵,其中每个单元(像素)非黑即白。 设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ,其中 r, c 分别代表子方阵左上角的行号和列号,size 是子方阵的边长。 若有多个满足条件的子方阵,返回 r 最小的,若 r 相同,返回 c 最小的子方阵。 若无满足条件的子方阵,返回空数组。

matrix.length == matrix[0].length <= 200

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/max-black-square-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

类似题目:LeetCode 1139. 最大的以 1 为边界的正方形(DP)

  • 求得每个坐标位置处的 上方、左侧 连续的0 有多少个
  • 从右下角开始遍历每个位置,每个点的初始边长edge取 min(上、左)
  • 检测另外两条边是不是也 >= edge
class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& mat) {
    	if(mat.size()==0 || mat[0].size() == 0)
    		return {};
    	int m = mat.size(), n = mat[0].size(), i, j, k;
    	vector<vector<int>> sumof0Up(m, vector<int>(n,0));//向上连续0个数
    	vector<vector<int>> sumof0Left(m, vector<int>(n,0));//向左连续0个数
    	for(i = 0; i < m; i++)
    	{
    		for(j = 0; j < n; j++)
    		{
    			if(mat[i][j] == 0)
    			{
    				if(i==0 && j==0)
    					sumof0Left[i][j] = 1, sumof0Up[i][j] = 1;
    				else if(i==0 && j>0)
    				{
    					sumof0Left[i][j] = sumof0Left[i][j-1]+1;
    					sumof0Up[i][j] = 1;
    				}
    				else if(j==0 && i > 0)
    				{
    					sumof0Left[i][j] = 1;
    					sumof0Up[i][j] = sumof0Up[i-1][j]+1;
    				}
    				else
    				{
    					sumof0Left[i][j] = sumof0Left[i][j-1]+1;
    					sumof0Up[i][j] = sumof0Up[i-1][j]+1;
    				}
    			}
    		}
    	}
    	vector<int> ans(3,-1);
    	int edge, x, y;
    	for(i = m-1; i >= 0; i--)
    	{
    		for(j = n-1; j >= 0; --j)
    		{
    			edge = min(sumof0Up[i][j], sumof0Left[i][j]);
    			//初始边长
    			while(edge > 0)
    			{
    				if(ans[2] > edge)//肯定小,不必检查了
    					break;
    				x = i-edge+1;//上方边的x
    				y = j-edge+1;//左侧边的y
    				if(sumof0Up[i][y]>=edge && sumof0Left[x][j]>=edge)
    				{	//左侧边  上侧边长都大于等 edge
    					if(edge > ans[2])
    					{
    						ans[2] = edge;
    						ans[0] = x;
    						ans[1] = y;
    					}
    					else if(edge == ans[2] && x <= ans[0])
    					{
    						if(x < ans[0])
    						{
    							ans[0] = x;
    							ans[1] = y;
    						}
    						else if(x == ans[0] && y < ans[1])
    							ans[1] = y;
    					}
    				}
                    edge--;//遍历所有可能
    			}
    		}
    	}
        if(ans[0]==-1)
            return {};
    	return ans;
    }
};

108 ms 19.2 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1363. 形成三的最大倍数(贪心,难)

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    Michael阿明
  • LeetCode 984. 不含 AAA 或 BBB 的字符串(贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-without-aaa-or-bbb ...

    Michael阿明
  • LintCode 386. 最多有k个不同字符的最长子字符串(双指针)

    100% 数据通过测试 总耗时 302 ms 您的提交打败了 41.40% 的提交!

    Michael阿明
  • 如何通过CM升级Kafka0.11及Spark2.2

    在前面的文章《CDH5.13和CM5.13的新功能》中Fayson介绍过Cloudera发布CDH5.13时,同时也发布了Kafka3.0版本(即社区0.11版...

    Fayson
  • 【cf789D】Weird journey(欧拉路、计数)

    n个点m条边无重边有自环无向图,问有多少种路径可以经过m-2条边两次,其它两条边1次。边集不同的路径就是不同的。

    饶文津
  • 速读原著-TCP/IP(TCP经受时延的确认)

    在图1 9 - 2中有一些与本节将要论及的时间有关的细微之处。图 1 9 - 3表示了图1 9 - 2中数据交换的时间系列(在该时间系列中,去掉了所有的窗口通告...

    cwl_java
  • 高通加大5G应用力度:发布又一款手机芯片,还推出机器人和无人机5G系统

    今天,高通推出了一个可用于机器人和无人机的5G系统——RB5。而就在昨天,刚发布又一款手机芯片骁龙690。

    量子位
  • 钞票找零-贪心,动态规划算法

    钞票找零问题是一个非常古老的问题,百度那些都有,本文将一步步的讲解关于钞票找零的算法以及优化过程.

    仙士可
  • 算法细节系列(26):区间

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 如何从Helm v2迁移到Helm v3

    Helm V3 版本已经发布了第三个 Beta 版本了,由于 V2 和 V3 版本之间的架构变化较大,所以如果我们现在正在使用 V2 版本的话,要迁移到 V3 ...

    CNCF

扫码关注云+社区

领取腾讯云代金券