回复: 14
跳转到指定楼层
上一主题 下一主题
收起左侧

Intuit Coding competition 试题

全局:

2017(10-12月) 码农类General 硕士 实习@intuit - Other - 在线笔试  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Intuit 网上coding competition的一道题给一个矩阵,矩阵里的每个元素是1,但是其中分布着一些长方形区域, 这些长方形区
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
,
[1,3,3,3],
[2,5,3,5],
[4,1,4,2]
]

评分

参与人数 1大米 +2 收起 理由
aiping373niu + 2 很有用的信息!

查看全部评分


上一篇:Akuna 电面
下一篇:狗家residency背靠背
推荐
 楼主| mwally 2017-10-26 02:40:18 | 只看该作者
全局:
Roxy83 发表于 2017-10-25 06:51
楼主求问思路是什么?谢谢!

我的思路是:从第一行开始遍历,如果当前点是0,说明这边有个矩形框,则开始找这个矩形框。第一个碰到的0一定是左上角的0,任务是找到右下角的0即可。找右下角的0就用广搜或者深搜,直到找到右下角(特征是这个0的右边和下边相邻的数字是1)。

附上我的c++代码:
void count(const vector<vector<int>>& image, vector<vector<int>>& visited, int i, int j, vector<int> &res){
  if(i<0 || j<0 || i>=image.size() || j>=image[0].size() || image[i][j] == 1 || (image[i][j] == 0 && visited[i][j] == 1) return;
      visited[i][j] = 1;
     count(image, visited, i-1, j, res);
     count(image, visited, i+1, j, res);
     count(image, visited, i, j-1, res);
     count(image, visited, i, j+1, res);
     if((i==image.size()-1 || image[i+1][j] == 1)&& (j==image[0].size()-1 || image[i][j+1] == 1){
       res.push_back(i);
       res.push_back(j);
     }
    return;
  
}

vector<vector<int>> getRectangleCoordinates(const vector<vector<int>>& image) {
  // IMPLEMENTATION GOES HERE
  vector<vector<int>> result;
  int r = image.size(), c = image[0].size();
  vector<vector<int>> visited(r,vector<int>(c,0));
  for(int i = 0; i < r; i++){
    for(int j = 0; j < c; j++){
      if(image[i][j] == 0 && visited[i][j] == 0){
        visited[i][j] = 1;
        vector<int> cur;
        cur.push_back(i);
        cur.push_back(j);
        count(image, visited, i, j, cur);
        result.push_back(cur);
      }
    }
  }
   
  return result;
}

评分

参与人数 1大米 +5 收起 理由
alice12 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
 楼主| mwally 2017-10-26 02:47:46 | 只看该作者
全局:
Roxy83 发表于 2017-10-26 02:43
我好好看看,太感谢了!

补充内容 (2017-10-26 02:44):

我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。
  1. void count(const vector<vector<int>>& image, vector<vector<int>>& visited, int i, int j, vector<int> &res){
  2.   if(i<0 || j<0 || i>=image.size() || j>=image[0].size() || image[i][j] == 1 || (image[i][j] == 0 && visited[i][j] == 1) return;
  3.       visited[i][j] = 1;
  4.      count(image, visited, i-1, j, res);
  5.      count(image, visited, i+1, j, res);
  6.      count(image, visited, i, j-1, res);
  7.      count(image, visited, i, j+1, res);
  8.      if((i==image.size()-1 || image[i+1][j] == 1)&& (j==image[0].size()-1 || image[i][j+1] == 1){
  9.        res.push_back(i);
  10.        res.push_back(j);
  11.      }
  12.     return;
  13.   
  14. }

  15. vector<vector<int>> getRectangleCoordinates(const vector<vector<int>>& image) {
  16.   // IMPLEMENTATION GOES HERE
  17.   vector<vector<int>> result;
  18.   int r = image.size(), c = image[0].size();
  19.   vector<vector<int>> visited(r,vector<int>(c,0));
  20.   for(int i = 0; i < r; i++){
  21.     for(int j = 0; j < c; j++){
  22.       if(image[i][j] == 0 && visited[i][j] == 0){
  23.         visited[i][j] = 1;
  24.         vector<int> cur;
  25.         cur.push_back(i);
  26.         cur.push_back(j);
  27.         count(image, visited, i, j, cur);
  28.         result.push_back(cur);
  29.       }
  30.     }
  31.   }
  32.    
  33.   return result;
  34. }
复制代码

评分

参与人数 1大米 +3 收起 理由
yunyunhello + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
nagisafight 2017-11-3 13:48:37 | 只看该作者
全局:
mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

楼主代码有错误,getRectangleCoordinates里面的if里面不能马上赋值visited为1,这样count执行即退出,visited=1该行应删掉
回复

使用道具 举报

🔗
Roxy83 2017-10-25 06:51:08 | 只看该作者
全局:
楼主求问思路是什么?谢谢!
回复

使用道具 举报

🔗
Roxy83 2017-10-26 02:43:11 | 只看该作者
全局:
mwally 发表于 2017-10-26 02:40
我的思路是:从第一行开始遍历,如果当前点是0,说明这边有个矩形框,则开始找这个矩形框。第一个碰到的0 ...

我好好看看,太感谢了!

补充内容 (2017-10-26 02:44):
对了,请问他给的input就是vector<vector<int>>& image吧?然后出去也是一个vector<vector<int>>表示坐标
对吧?
回复

使用道具 举报

🔗
Roxy83 2017-10-26 02:50:23 | 只看该作者
全局:
mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

OK 楼主好人!祝好运~
回复

使用道具 举报

🔗
Roxy83 2017-10-26 10:39:15 | 只看该作者
全局:
mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

楼主你这段代码过了test case吗 我用java写了一遍 感觉答案有点不对呢?
回复

使用道具 举报

🔗
 楼主| mwally 2017-10-26 13:38:55 | 只看该作者
全局:
Roxy83 发表于 2017-10-26 10:39
楼主你这段代码过了test case吗 我用java写了一遍 感觉答案有点不对呢?

我过test case了啊。。。
回复

使用道具 举报

🔗
 楼主| mwally 2017-10-26 13:44:07 | 只看该作者
全局:
mwally 发表于 2017-10-26 13:38
我过test case了啊。。。

我记得我缺括号?因为我断网了两次所以存下了第一次断网前的代码。。 后来就没有再改这个文档了。但我记得我就括号有问题,程序思路没改
回复

使用道具 举报

🔗
point8808 2017-10-27 05:14:31 | 只看该作者
全局:
一定要遍历四个方向么?如果是找右下角的话 不是两个方向就可以了嘛
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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