https://leetcode.com/tag/depth-first-search/
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
class Solution {
int dfs(vector<vector<int>>& matrix, vector<vector<int> > & visited, int x, int y) {
if(visited[x][y] != -1)
return visited[x][y];
int res = 1;
//left
if(y > 0 && matrix[x][y-1] > matrix[x][y])
res = max(res, dfs(matrix, visited, x, y-1) + 1) ;
//right
if(y < matrix[0].size() - 1 && matrix[x][y+1] > matrix[x][y])
res = max(res, dfs(matrix, visited, x, y+1) + 1);
//up
if(x > 0 && matrix[x-1][y] > matrix[x][y])
res = max(res, dfs(matrix, visited, x-1, y) + 1);
//down
if(x < matrix.size() - 1 && matrix[x+1][y] > matrix[x][y])
res = max(res, dfs(matrix, visited, x+1, y) + 1);
visited[x][y] = res;
return res;
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if(m == 0) return 0;
int n = matrix[0].size();
if(n == 0) return 0;
vector<vector<int> > visited(m,vector<int>(n, -1));
int res = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
res = max(res, dfs(matrix, visited, i, j));
return res;
}
};
https://leetcode.com/problems/maximum-depth-of-binary-tree/
递归版本：
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
return max(maxDepth(root->left),maxDepth(root->right)) + 1;
}
};
非递归版本(bfs)：
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
queue<TreeNode *> nodeQueue;
int res = 0;
nodeQueue.push(root);
while(!nodeQueue.empty()) {
res++;
int tmpsize= nodeQueue.size();
for(int i = 0; i < tmpsize; i++) {
TreeNode * temp = nodeQueue.front();
nodeQueue.pop();
//cout<<"res="<<res<<"; node="<<temp->val<<endl;
if(temp->left != NULL) nodeQueue.push(temp->left);
if(temp->right != NULL) nodeQueue.push(temp->right);
}
}
return res;
}
};
same tree
https://leetcode.com/problems/same-tree/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q == NULL) return true;
if(p == NULL || q == NULL) return false;
if(p->val != q->val) return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};
https://leetcode.com/problems/balanced-binary-tree/
这个方法感觉不好，在不停的进行重复的遍历：
class Solution {
int getHeight(TreeNode * root) {
if(root == NULL) return 0;
return max(getHeight(root->left),getHeight(root->right)) + 1;
}
public:
bool isBalanced(TreeNode* root) {
if(root == NULL) return true;
int l = getHeight(root->left);
int r = getHeight(root->right);
if(abs(l-r) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return true;
return false;
}
};
https://leetcode.com/discuss/22898/the-bottom-up-o-n-solution-would-be-better
class solution {
public:
int dfsHeight (TreeNode *root) {
if (root == NULL) return 0;
int leftHeight = dfsHeight (root -> left);
if (leftHeight == -1) return -1;
int rightHeight = dfsHeight (root -> right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return max (leftHeight, rightHeight) + 1;
}
bool isBalanced(TreeNode *root) {
return dfsHeight (root) != -1;
}
};
https://leetcode.com/problems/number-of-islands/
dfs, bfs, union find
dfs：
class Solution {
void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int x, int y) {
if(visited[x][y])
return;
visited[x][y] = true;
//up
if(x > 0 && grid[x-1][y] == '1')
dfs(grid, visited, x-1, y);
//down
if(x < grid.size() - 1 && grid[x+1][y] == '1')
dfs(grid, visited, x+1, y);
//left
if(y > 0 && grid[x][y-1] == '1')
dfs(grid, visited, x, y-1);
//right
if(y < grid[0].size() - 1 && grid[x][y+1] == '1')
dfs(grid, visited, x, y+1);
}
public:
int numIslands(vector<vector<char>> &grid) {
int m = grid.size();
if(m == 0) return 0;
int n = grid[0].size();
if(n == 0) return 0;
vector<vector<bool> > visited(m,vector<bool>(n,false));
int num = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, visited, i, j);
num++;
}
}
}
return num;
}
};
bfs:
class Solution {
void bfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int x, int y) {
queue<pair<int,int>> q;
q.push(make_pair(x,y));
visited[x][y] = true;
while(!q.empty()) {
auto i = q.front();
q.pop();
x = i.first;
y = i.second;
if(x > 0 && grid[x-1][y] == '1' && visited[x-1][y] == false) {
q.push(make_pair(x-1,y));
visited[x-1][y] = true;
}
if(x < grid.size() - 1 && grid[x+1][y] == '1' && visited[x+1][y] == false) {
q.push(make_pair(x+1,y));
visited[x+1][y] = true;
}
if(y > 0 && grid[x][y-1] == '1' && visited[x][y-1] == false) {
q.push(make_pair(x,y-1));
visited[x][y-1] = true;
}
if(y < grid[0].size() - 1 && grid[x][y+1] == '1' && visited[x][y+1] == false) {
q.push(make_pair(x,y+1));
visited[x][y+1] = true;
}
}
}
public:
int numIslands(vector<vector<char>> &grid) {
int m = grid.size();
if(m == 0) return 0;
int n = grid[0].size();
if(n == 0) return 0;
vector<vector<bool> > visited(m,vector<bool>(n,false));
int num = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1' && !visited[i][j]) {
bfs(grid, visited, i, j);
num++;
}
}
}
return num;
}
};
union-find:
class Solution {
vector<int> roots;
int findRoot(int idx) {
while(roots[idx] != idx)
idx = roots[idx];
return idx;
}
public:
int numIslands(vector<vector<char>> &grid) {
int m = grid.size();
if(m == 0) return 0;
int n = grid[0].size();
if(n == 0) return 0;
roots.resize(m * n, -1);
vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int num = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] == '1') {
roots[i * n + j] = i * n + j;
num++;
}
cout<<"num="<<num<<endl;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '0')
continue;
int id_old = i * n + j;
for (auto & d:dirs) {
if(i + d[0] < 0 || i + d[0] >= m || j + d[1] < 0 || j + d[1] >= n)
continue;
if(grid[i + d[0]][j + d[1]] == '0')
continue;
int id_new = (i + d[0]) * n + (j + d[1]);
int root_new = findRoot(id_new);
int root_old = findRoot(id_old);
if(root_new != root_old) {
roots[root_new] = root_old;
num--;
}
}
}
}
return num;
}
};
number of island ii:
https://leetcode.com/problems/number-of-islands-ii/
class Solution {
vector<int> parents;
int num;
void uf(int old_id, int new_id) {
int old_root = find(old_id);
int new_root = find(new_id);
if(old_root != new_root) {
parents[old_root] = new_root;
num--;
}
}
int find(int id) {
while(parents[id] != id)
id = parents[id];
return id;
}
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
parents.resize(m * n, -1);
vector<int> res;
num = 0;
for(auto &i : positions) {
int x = i.first;
int y = i.second;
int id = x * n + y;
parents[id] = id;
num++;
if(x > 0 && parents[(x - 1) * n + y] != -1)
uf(id, (x - 1) * n + y);
if(x < m - 1 && parents[(x + 1) * n + y] != -1)
uf(id, (x + 1) * n + y);
if(y > 0 && parents[x * n + (y - 1)] != -1)
uf(id, x * n + (y - 1));
if(y < n - 1 && parents[x * n + (y + 1)] != -1)
uf(id, x * n + (y + 1));
res.push_back(num);
}
return res;
}
};
网友评论