一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1411|回复: 4
收起左侧

[算法题] 一道OA难题求解

[复制链接] |试试Instant~ |关注本帖
忆梦前尘 发表于 2016-3-11 05:19:15 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目是这样的。

一个boolean的M*N二维矩阵,由1和0组成。要求找出全部由1组成的正方形,从左上角开始,每次向右或者向下移动一格,到达右下角,途中不能遇到任何0。求满足这样条件最大的正方形的面积。

1 1 1 0
1 1 1 1
1 1 1 1
0 1 1 1
0 1 1 1

这个例子中,最大的面积是4,即2*2的矩形。
这题跟leetcode里的max rectangle area有点像,但是不同的是,那题会返回3*3,但是这题不行,因为中途3*3的矩形过不来。可以想成推箱子的游戏,求能通过的最大的箱子的size。

所以有人能帮忙想想该怎么做吗? 提示的worst case runtime 是 O(m*n*log(m+n)), 空间是 O(m*n)

ccarter 发表于 2016-3-13 22:33:29 | 显示全部楼层
应该是先预处理以每个点为左上角的最大正方形边长,然后二分答案

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

 楼主| 忆梦前尘 发表于 2016-3-14 01:48:44 | 显示全部楼层
ccarter 发表于 2016-3-13 06:33
应该是先预处理以每个点为左上角的最大正方形边长,然后二分答案

哦,这个二分是怎么个二分法?比如例子里面以左上角为顶点的正方形可以是1,2,3.那么应该二分这个1,2,3么?
回复 支持 反对

使用道具 举报

ccarter 发表于 2016-3-14 23:48:49 | 显示全部楼层
忆梦前尘 发表于 2016-3-14 01:48
哦,这个二分是怎么个二分法?比如例子里面以左上角为顶点的正方形可以是1,2,3.那么应该二分这个1,2, ...

嗯,二分1~3,因为这个答案有这样的性质:如果答案为k,则任何小于等于k的一定能过去,任何大于k的一定过不去
但是我还没太想好预处理怎么O(mn)
回复 支持 反对

使用道具 举报

WLLiu 发表于 2016-3-15 06:43:07 | 显示全部楼层
check min(m,n)
if passable
    return min(m,n)
else
    h = min(m,n)
    l = 1
    m = (h+l) / 2
    while( h > l )
        check(m)
        if(passable)
            l = m + 1
        else
            h = m - 1
    end while
    return m

这样就行了。check(l)是检查变长为l的正方形能否从左上角通过到右下角,耗时O(mn),dfs搜索就行。一共检查log(min(m,n))次。
空间上,储存这个map要O(mn)所以就是O(mn)复杂度。
你们看对不对?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 05:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表