Google Interview - Flowing Water
2288 단어 interview
Suppose the left and top side of the matrix is surrounded by Pacific, the right and bottom is Atlantic.
Please write a function and return all lakes that can flow to both Pacific and Atlantic.
For example:
Pacific: ~
Atlantic: *
~ ~ ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * * *
The elements in parentheses are expected outputs:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
/*
struct Point {
int x{ 0 }, y{ 0 };
};
*/
vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
void dfs(vector<vector<int>>& mat, unordered_set<Point>& ocean, Point p) {
int n = mat.size();
ocean.insert(p);
for(auto& dir:dirs) {
int x = p.x+dir[0];
int y = p.y+dir[1];
if(x<0 || y<0 || x>=n || y>=n || mat[x][y]<mat[p.x][p.y] || ocean.count({x,y})) continue;
dfs(mat, ocean, {x,y});
}
}
vector<Point> flowing_water(vector<vector<int>>& mat) {
unordered_set<Point> pac, atl;
int n = mat.size();
for(int i=0; i<n; i++) {
dfs(mat, pac, {0, i});
dfs(mat, pac, {i, 0});
dfs(mat, atl, {n-1, i});
dfs(mat, atl, {i, n-1});
}
vector<Point> res;
// unordered results
// for(auto& p:atl) {
// if(pac.count(p)) {
// res.push_back(p);
// }
// }
// ordered results
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
Point p = {i, j};
if(pac.count(p) && atl.count(p)) {
res.push_back(p);
}
}
}
return res;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 1000 개 노크 #2. Longest common substringsProblem Solution DP (다이나믹 프로그래밍) 중에서 고전적인 문제입니다. 두 문자열을 S1과 S2, 각각의 길이를 M, N으로 설정합니다. 총당으로 S1에서 모든 부분 문자열을 추출하고, 그것들이 S2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.