Intuit Coding competition 试题

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]
]

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;
}

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

复制代码

mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

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

楼主求问思路是什么？谢谢！

mwally 发表于 2017-10-26 02:40
我的思路是：从第一行开始遍历，如果当前点是0，说明这边有个矩形框，则开始找这个矩形框。第一个碰到的0 ...

我好好看看，太感谢了！

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

mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

OK 楼主好人！祝好运～

mwally 发表于 2017-10-26 02:47
我突然发现 上面的代码出现斜体的地方的【i】都不见了。。。你看下面这个代码。。

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

Roxy83 发表于 2017-10-26 10:39
楼主你这段代码过了test case吗 我用java写了一遍 感觉答案有点不对呢？

我过test case了啊。。。

mwally 发表于 2017-10-26 13:38
我过test case了啊。。。

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

一定要遍历四个方向么？如果是找右下角的话 不是两个方向就可以了嘛