Bloomberg电面

aojing 发表于 2016-6-3 06:31
没看懂题，，为什么是返回10？

多谢安慰啊~不过我觉得肯定跪了，刚面完五分钟的时候想到中间更新ｒｅｓｕｌｔ的时候貌似更新错了

ptbrxlphx 发表于 2016-6-3 08:10
时间复杂度为所有点的个数

我用的是BFS, 找到所有可以reach的3的点，中间不断地更新现在得到的3组成图形的边数

这是后来才想到的，当时面的时候跟新错了，没考虑完全

chplushsieh 发表于 2016-6-3 16:42
找出「所有」為3的點，好像有點不對。我理解是：只有和題目給定的matrix[2][1]相連的3，才納入考慮。所以 ...

是的，找到所有从<x,y> 能reach的3的点组成的图形
我用的是BFS，中间不断地更新当前的图形的边数

aojing 发表于 2016-6-3 06:31
没看懂题，，为什么是返回10？

同学看下面的评论吧，我回复了。
就是所有能reach的所有3组成的图形的边长

int cal(vector<vector<int>> &g, int a, int b)
{
    int n=g.size();
    if(!n)return 0;
    int m=g[0].size();
    if(!m) return 0;
    queue<pair<int,int>> q;
    int k=g[a][b];
    int res=0;
    q.emplace(a,b);
    const vector<int> d={0,1,0,-1,0};
    while(q.size())
    {
        int i=q.front().first, j=q.front().second;
        int ct=0;
        q.pop();
        if(g[i][j]==-k) continue;
        for(int cc=0;cc<4;cc++)
        {
            int ii=i+d[cc], jj=j+d[cc+1];
            if(ii<0||ii>=n||jj<0||jj>=m) continue;
            if(g[ii][jj]==k||g[ii][jj]==-k) ct++;
            if(g[ii][jj]==k)
                q.emplace(ii,jj);
        }
        g[i][j]=-k;
        res+=(4-ct);
    }
    return res;
}

用C++写了一个DFS版本的，仅供参考
void helper(vector<vector<int>> & board, vector<vector<int>> & visited, int r, int c, int target, vector<int> & result, vector<pair<int, int>> & dir)
{
        if (r >= 0 && r<board.size() && c >= 0 && c<board[0].size()){
                if (visited[r][c] == 0 && board[r][c] == target){
                        //update four value;
                        if (r>result[0])
                                result[0] = r;
                        if (r<result[1])
                                result[1] = r;
                        if (c<result[2])
                                result[2] = c;
                        if (c>result[3])
                                result[3] = c;

                        visited[r][c] = 1;

                        for (auto d : dir){
                                helper(board, visited, r + d.first, c + d.second, target, result, dir);
                        }
                }
        }

        return;
}


int findMaxRec(vector<vector<int>> & board, int i, int j)
{
        //iterate every connected target and update the left, right, top, bottom value.

        //DFS
        vector<int> result = { i, i, j, j }; //bottom, top, left, right
        int target = board[i][j];
        vector<vector<int>> visited(board.size(), vector<int>(board[0].size(), 0));
        vector<pair<int, int>> dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        helper(board, visited, i, j, target, result, dir);

        return (result[0] - result[1] + 1 + result[3] - result[2] + 1) * 2;
}

int main()
{
        vector<vector<int>> board = { { 0, 1, 2, 3, 4 }, { 0, 3, 0, 1, 7 }, { 0, 3, 0, 1, 7 }, { 0, 3, 3, 1, 7 } };
        cout<<findMaxRec(board, 2, 1);

        system("pause");
        return 0;
}

不是说B家主要考C/C++吗？

DFS找到所有不重复的符合条件的点，设置一个数为num=0，每找到一个点，这个数num-2.
点的个数*4-num就是答案。

感谢楼主分享~~~

请问
3 1 2 3 4
3 3 0 1 7
3 3 0 1 7
0 3 3 1 7  如果长这样的话 应该返回的边长是不是12？

补充内容 (2016-8-15 00:51):
还是应该是14？。。 题目理解我还是有点问题 bb现在怎么这么难了>.<,,...