聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1867|回复: 5
收起左侧

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

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

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

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

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

查看全部评分

回复 支持 3 反对 0

使用道具 举报

全球28万学生4.7分推荐
619899442 发表于 2017-12-7 05:18:48 | 显示全部楼层
本帖最后由 619899442 于 2017-12-7 05:21 编辑

我有一个不成熟的小想法:使用DP实现:
假设DP[j] 代表可以从左上角移动到(i, j) 的最大正方形,那么有三种方式使它移动到(i, j):
1. 无需移动
2. 从左到右
3. 从上到下

但是这样做的复杂度是O(mn), 跟楼主给的不太一样,所以我并不是很确定
  1. public class MaxMoveableRect {

  2.     private static int MaxMoveableRect(int [][] matrix) {
  3.         int m = matrix.length;
  4.         int n = matrix[0].length;
  5.         // allOnes[i][j] == whether the rectangle defined by (0,0) and (i, j) only
  6.         // contains 1
  7.         boolean [][] allOnes = new boolean [m][n];
  8.         allOnes[0][0] = (matrix[0][0] == 1) ? true: false;
  9.         for (int i = 1; i < m; ++i) {
  10.             allOnes[i][0] = allOnes[i-1][0] && (matrix[i][0] == 1);
  11.         }
  12.         for (int j = 1; j < n; ++j) {
  13.             allOnes[0][j] = allOnes[0][j-1] && (matrix[0][j] == 1);
  14.         }
  15.         for (int i = 1; i < m; ++i) {
  16.             for (int j = 1; j < n; ++j) {
  17.                 allOnes[i][j] = allOnes[i][j-1] && allOnes[i-1][j] && (matrix[i][j] == 1);
  18.             }
  19.         }

  20.         // ceiling[i][j] -- the row index of the ceiling 0 above matrix[i][j]
  21.         int [][] ceiling = new int [m][n];
  22.         for (int j = 0; j < n; ++j) {
  23.             ceiling[0][j] = (matrix[0][j] == 0) ? 0 : -1;
  24.         }
  25.         for (int i = 1; i < m; ++i) {
  26.             for (int j = 0; j < n; ++j) {
  27.                 ceiling[i][j] = (matrix[i][j] == 0) ? i : ceiling[i-1][j];
  28.             }
  29.         }

  30.         // tail[i][j] -- the col index if the tail (righmost) 0 on the left of matrix[i][j]
  31.         int [][] tail = new int [m][n];
  32.         for (int i = 0; i < m; ++i) {
  33.             tail[i][0] = (matrix[i][0] == 0) ? 0 : -1;
  34.         }
  35.         for (int i = 0; i < m; ++i) {
  36.             for (int j = 1; j < n; ++j) {
  37.                 tail[i][j] = (matrix[i][j] == 0) ? j : tail[i][j-1];
  38.             }
  39.         }




  40.         // the max edge length of all-one sequre that can be moved from (0, 0) to
  41.         // (i, j)
  42.         int [][] dp = new int [m][n];
  43.         dp[0][0] =  (matrix[0][0] == 1) ? 1 : 0;
  44.         for (int i = 1; i < m; ++i) {
  45.             dp[i][0] = (matrix[i][0] == 1) ? dp[i-1][0] : 0;
  46.         }
  47.         for (int j = 1; j < n; ++j) {
  48.             dp[0][j] = (matrix[0][j] == 1) ? dp[0][j-1] : 0;
  49.         }
  50.         for (int i = 1; i < m; ++i) {
  51.             for (int j = 1; j < n; ++j) {
  52.                 if (matrix[i][j] == 0) {
  53.                     dp[i][j] = 0;
  54.                 } else if (allOnes[i][j]) {
  55.                     dp[i][j] = Math.min(i + 1, j + 1);
  56.                 } else {
  57.                     dp[i][j] = Math.max(
  58.                         Math.min(dp[i][j-1], i - ceiling[i][j]),  // move from left to right
  59.                         Math.min(dp[i-1][j], j - tail[i][j])
  60.                     );
  61.                 }
  62.             }
  63.         }

  64.         return dp[m-1][n-1];
  65.     }


  66.     public static void main(String [] args) {

  67.         int [][] matrix = new int [][] {
  68.             {1,1,1,0},
  69.             {1,1,1,1},
  70.             {1,1,1,1},
  71.             {0,1,1,1},
  72.             {0,1,1,1}
  73.         };
  74.         System.out.println(MaxMoveableRect(matrix));

  75.     }

  76. }
复制代码

回复 支持 1 反对 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

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-21 11:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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