s*******3
发帖数: 6 | 1 从同学那边问来的一道Google面经题
输入是一个 N*N的矩阵，代表地势高度（elevation）。然后如果下雨，水流只能流去
比他矮或者一样高的地势。矩阵上边和左边是太平洋，下边和右边是大西洋。求出所有
的能同时流到两个大洋的点。
求讨论，求指导。 | f*******w
发帖数: 1243 | 2 initialize一个NxN矩阵, 全为0
从上面和左边每个点开始做dfs，（走过的就不走了）碰到更高的点就++value
从右边和下面每个点开始做dfs，碰到更高的点就++value
扫一遍矩阵，把value为2的点输出 | P********s
发帖数: 19 | 3 是不是可以把问题细分成四个子问题：可以到上，下，左，右的点分别有哪些。解决其
中一个，另外三个也就解决了，最后能同时到大西洋和太平洋的点也自然解决了。
以第一个子问题为例(求出所有可以到上面的点）：先把所有除了第一行的点设定为“
不能流到上面”，第一行的点设定为“可以”，从这第一行开始广搜，搜索深度上限设
为N*N，每一层的搜索都把可以流到上一层的点都设定为“可以”。搜索结束后所有标
记为“可以”的点就是满足要求的。然后类似地做另外三个方向。复杂度感觉是O（N*N）
【在 s*******3 的大作中提到】
: 从同学那边问来的一道Google面经题
: 输入是一个 N*N的矩阵，代表地势高度（elevation）。然后如果下雨，水流只能流去
: 比他矮或者一样高的地势。矩阵上边和左边是太平洋，下边和右边是大西洋。求出所有
: 的能同时流到两个大洋的点。
: 求讨论，求指导。
| f*******w
发帖数: 1243 | 4 仔细想想其实都不用dfs，bfs，顺序扫就行了。相当于DP。 | h***k
发帖数: 161 | 5 大牛展开讲讲
【在 f*******w 的大作中提到】
: 仔细想想其实都不用dfs，bfs，顺序扫就行了。相当于DP。
| f*********0
发帖数: 17 | 6 实现了一下，用了dfs，略有不同的是：
上面左边做dfs时，value+1
右边下面dfs时，value+10
这样就用这个矩阵记录这轮dfs是否访问过这个节点。
所以这样每个节点最多被访问一次，复杂度为O(N*N);
代码求拍
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int N;
bool isValidIndex(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
void dfs(vector > &matrix, int set,
vector > &result, int x, int y) {
if (result[x][y] >= set) return;
result[x][y] += set;
for (int i = 0; i < 4; ++i) {
if (isValidIndex(x+dx[i], y+dy[i]) && matrix[x+dx[i]][y+dy[i]] >=
matrix[x][y]) {
dfs(matrix, set, result, x+dx[i], y+dy[i]);
}
}
}
vector> find(vector > &matrix) {
N = matrix.size();
vector > result(N, vector(N, 0));
for (int i = 0; i < N; ++i) {
dfs(matrix, 1, result, 0, i);
}
for (int i = 1; i < N; ++i) {
dfs(matrix, 1, result, i, 0);
}
for (int i = 0; i < N; ++i) {
dfs(matrix, 10, result, N-1, i);
}
for (int i = 0; i < N; ++i) {
dfs(matrix, 10, result, i, N-1);
}
vector > nodes;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (result[i][j] == 11) {
nodes.push_back({i, j});
}
}
}
return nodes;
} | c****m
发帖数: 179 | 7 其实双向bfs就可以。
再简化一下就是ls说的dp。N^2
先把左边和上边的置为true，然后往右边和下边扫根据高度决定是否当前点为true
然后再从右边和下边往左上扫，遇到true就输出，要注意边界。
这个过程是dp。 | z*********e
发帖数: 10149 | 8 DP不行吧，我觉得DFS/BFS是个不错的办法
比如说这样的grid
3 2 1
4 5 1
5 6 1
6 6 6
用DP不能判断(2,0)那个位置的5可以流到大西洋去 | x********k
发帖数: 256 | 9 Union find吧。
【在 s*******3 的大作中提到】
: 从同学那边问来的一道Google面经题
: 输入是一个 N*N的矩阵，代表地势高度（elevation）。然后如果下雨，水流只能流去
: 比他矮或者一样高的地势。矩阵上边和左边是太平洋，下边和右边是大西洋。求出所有
: 的能同时流到两个大洋的点。
: 求讨论，求指导。
| s*******3
发帖数: 6 | 10 大神能详细说一说么。谢谢！
【在 x********k 的大作中提到】
: Union find吧。
| | | w*******i
发帖数: 186 | 11 那位大神的意思应该是，不管用bfs或dfs，从两边分别找能够到达的区域，当成两个集
合，然后求并集。需要用并查集这种数据结构优化。
简单的双向bfs适合探索这个题是否有解，但不能返回所有要输出的点。
【在 s*******3 的大作中提到】
: 大神能详细说一说么。谢谢！
| f*********0
发帖数: 17 | 12 就是双向dfs,然后求union吧？
【在 w*******i 的大作中提到】
: 那位大神的意思应该是，不管用bfs或dfs，从两边分别找能够到达的区域，当成两个集
: 合，然后求并集。需要用并查集这种数据结构优化。
: 简单的双向bfs适合探索这个题是否有解，但不能返回所有要输出的点。
| G*********n
发帖数: 53 | 13 ...难道是从我这传出去的。。。。 标准DFS * 2， 想下怎么建图就行了 | a***n
发帖数: 623 | 14 有个问题要先问清楚吧
比如这个矩阵
1 2 3
4 5 6
7 8 9
在5号点的降雨是仅仅会流向1（最低点）呢还是会流向所有<5的点？（1,2,3,4） | i*****o
发帖数: 105 | 15 #include
#include
int x[10][10] = {
{ 1, 1, 1, 1, 1, 1, 5, 1, 1, 1,},
{ 1, 1, 1, 1, 1, 1, 4, 1, 1, 1,},
{ 1, 1, 1, 1, 1, 1, 8, 1, 1, 1,},
{ 1, 1, 1, 1, 5, 4, 10, 1, 1, 1,},
{ 1, 1, 1, 1, 4, 1, 10, 10, 1, 1,},
{ 1, 1, 1, 1, 5, 5, 10, 10, 10, 10,},
{ 1, 1, 5, 6, 1, 5, 11, 1, 1, 1,},
{ 1, 1, 3, 1, 1, 1, 10, 1, 1, 1,},
{ 1, 2, 2, 1, 1, 1, 1, 1, 1, 1,},
{ 2, 1, 10, 10, 10, 10, 10, 10, 1, 1,},
};
#define PA 0x01
#define AT 0x02
struct dot {
int x;
int y;
};
detect_line2(int N, int g[N][N], int a[N][N], int s,
struct dot start[], int set_bit)
{
struct dot nextline[2*N], myline[2*N];
int n, m, i;
for (i = 0; i < s; i++) {
a[start[i].x][start[i].y] |= set_bit;
}
memcpy(myline, start, sizeof(struct dot) * s);
n = s;
again:
m = 0;
for (i = 0; i < n; i++) {
int x = myline[i].x, y = myline[i].y;
if (x-1 >= 0) {
if (!(a[x-1][y] & set_bit) && g[x-1][y] >= g[x][y]) {
nextline[m].x = x-1;
nextline[m].y = y;
a[x-1][y] |= set_bit;
m++;
}
}
if (x+1 < N) {
if (!(a[x+1][y] & set_bit) && g[x+1][y] >= g[x][y]) {
nextline[m].x = x+1;
nextline[m].y = y;
a[x+1][y] |= set_bit;
m++;
}
}
if (y-1 >= 0) {
if (!(a[x][y-1] & set_bit) && g[x][y-1] >= g[x][y]) {
nextline[m].x = x;
nextline[m].y = y - 1;
a[x][y-1] |= set_bit;
m++;
}
}
if (y+1 < N) {
if (!(a[x][y+1] & set_bit) && g[x][y+1] >= g[x][y]) {
nextline[m].x = x;
nextline[m].y = y+1;
a[x][y+1] |= set_bit;
m++;
}
}
}
if (m == 0) {
return;
} else {
n = m;
memcpy(myline, nextline, sizeof(struct dot) * m);
goto again;
}
}
detect2(int G, int g[G][G])
{
int a[G][G];
int i, j, n = 0;
struct dot myline[2*G];
memset(a, 0, sizeof(a));
for (i= 0; i< G; i++) {
myline[n].x = i;
myline[n].y = G-1;
n++;
}
detect_line2(G, g, a, n, myline, AT);
n = 0;
for (i= 0; i< G; i++) {
myline[n].x = i;
myline[n].y = 0;
n++;
}
detect_line2(G, g, a, n, myline, PA);
for (i = 0; i < G; i++) {
for (j = 0; j < G; j++) {
if (a[i][j] == (AT|PA)) {
printf("(%2d) ", g[i][j]);
} else {
printf(" %2d ", g[i][j]);
}
}
printf("\n");
}
}
detect_line(int G, int g[G][G], int a[G][G], int x, int y,
int last, int set_bit)
{
if (x < 0 || x >= G || y < 0 || y >= G) {
return;
}
if ((a[x][y] & set_bit)) {
return;
}
if (g[x][y] >= last) {
a[x][y] |= set_bit;
detect_line(G, g, a, x+1, y, g[x][y], set_bit);
detect_line(G, g, a, x-1, y, g[x][y], set_bit);
detect_line(G, g, a, x, y+1, g[x][y], set_bit);
detect_line(G, g, a, x, y-1, g[x][y], set_bit);
}
return;
}
detect(int G, int g[G][G])
{
int a[G][G];
int i, j;
memset(a, 0, sizeof(a));
for (i= 0; i< G; i++) {
detect_line(G, g, a, i, G-1, 0, AT);
}
for (i= 0; i< G; i++) {
detect_line(G, g, a, i, 0, 0, PA);
}
for (i = 0; i < G; i++) {
for (j = 0; j < G; j++) {
if (a[i][j] == (AT|PA)) {
printf("(%2d) ", g[i][j]);
} else {
printf(" %2d ", g[i][j]);
}
}
printf("\n");
}
}
main()
{
detect(10, x);
printf("\n");
detect2(10, x);
} | d*l
发帖数: 1810 | 16 走过的点就不走了 感觉不对。
应该是走过的点且value ++过就不走了
【在 f*******w 的大作中提到】
: initialize一个NxN矩阵, 全为0
: 从上面和左边每个点开始做dfs，（走过的就不走了）碰到更高的点就++value
: 从右边和下面每个点开始做dfs，碰到更高的点就++value
: 扫一遍矩阵，把value为2的点输出
| a********s
发帖数: 20 | 17 同意你这个做法。
我昨天也面到了。不过当时没相到，用了brute force的方法。就是遍历每一个点，做
DFS，如果既能到pacific，又能到atlantic，就输出。。。。面试官自己
在干自己的活，根本没理我，也没有说对不对。。不知道会不会悲剧了。。。
【在 c****m 的大作中提到】
: 其实双向bfs就可以。
: 再简化一下就是ls说的dp。N^2
: 先把左边和上边的置为true，然后往右边和下边扫根据高度决定是否当前点为true
: 然后再从右边和下边往左上扫，遇到true就输出，要注意边界。
: 这个过程是dp。
| p**p
发帖数: 742 | 18 The algorithm mentioned above cannot handle cases like:
{{1, 4, 4, 2},
{2, 1, 3, 1},
{2, 2, 2, 3},
{1, 2, 4, 2}}
in which the element at (1, 2) will be marked as false in the top-to-down,
left-to-right scan and therefore, not be included in the output. However, it
actually is a valid position.
Above algorithm can be changed as follows: mark top and left borders as true
, then scan from left to right, top to bottom. If an element is equal or
bigger than its up or left neighbors, mark it as true too. The result is
saved to a boolean matrix, say matrix 1. After finishing the whole matrix,
scan from right to left, bottom to top, if an element is equal or bigger
than its down or right neighbors, check the result in matrix 1, if true,
directly add it to the output. Otherwise, check if its down or right
neighbors in matrix 1 to see if it can be changed from false to true. If yes
, make the change in matrix 1 and add it to the output.
【在 a********s 的大作中提到】
: 同意你这个做法。
: 我昨天也面到了。不过当时没相到，用了brute force的方法。就是遍历每一个点，做
: DFS，如果既能到pacific，又能到atlantic，就输出。。。。面试官自己
: 在干自己的活，根本没理我，也没有说对不对。。不知道会不会悲剧了。。。
| p**p
发帖数: 742 | 19 嗯，这样好像也有问题。还是搞不定下面这种情况：
1 1 1 1 1 1
1 1 1 2 1 1
1 2 1 2 1 1
3 2 2 2 2 2
（2，2）里面的那个1在从下往上，从右往左扫描的时候不会被考虑，因为它比下面和
右面的元素都小。
看来还是老老实实DFS吧。
it
true
【在 p**p 的大作中提到】
: The algorithm mentioned above cannot handle cases like:
: {{1, 4, 4, 2},
: {2, 1, 3, 1},
: {2, 2, 2, 3},
: {1, 2, 4, 2}}
: in which the element at (1, 2) will be marked as false in the top-to-down,
: left-to-right scan and therefore, not be included in the output. However, it
: actually is a valid position.
: Above algorithm can be changed as follows: mark top and left borders as true
: , then scan from left to right, top to bottom. If an element is equal or
| o*****g
发帖数: 165 | 20 感觉可以用两次动态规划，分别求能到太平洋和大西洋的点
然后求交集 | p****a
发帖数: 447 | 21 没啥区别吧，无非就是能不能斜着走的问题
【在 a***n 的大作中提到】
: 有个问题要先问清楚吧
: 比如这个矩阵
: 1 2 3
: 4 5 6
: 7 8 9
: 在5号点的降雨是仅仅会流向1（最低点）呢还是会流向所有<5的点？（1,2,3,4）
| p****a
发帖数: 447 | 22 这题是求流到两个方向的，value==2才有意义
所以第一次走必然得value++ 的才是candidate
【在 d*l 的大作中提到】
: 走过的点就不走了 感觉不对。
: 应该是走过的点且value ++过就不走了
|
|
