owned this note
owned this note
Published
Linked with GitHub
# Leetcode刷題學習筆記--DFS/BFS
## DFS
自己呼叫自己達到DFS的效果。可以分成兩種形式。
1. TOP-BOTTOM 從上到下
```cpp
void dfs(node *root) {
// 先做運算
...
// 最後在呼叫自己
dfs(root->next);
}
```
2. BOTTOM-TOP 從下到上
```cpp
void dfs(node *root) {
// 先呼叫自己，則會先走訪到最後node
dfs(root->next);
// 最後在做運算判斷
...
}
```
例如 [110. Balanced Binary Tree](/Rs3M7lf1TzOR0Lx_RhgpNg#110-Balanced-Binary-Tree) 適合用bottom-top。
### 使用DFS偵測cyclic
1. 偵測graph上所有的path是否有cyclic，所以必須從每個node出發來檢查每條path。**必須從每個node出發，才可以走過每條path**
```cpp=
for(int i = 0; i < numNodes; ++i) {
if(hasCyclic(i)) return true;
}
return false;
```
2. 記錄每條path上找過的node，因為cyclic表示會走回到之前走過的node。
```cpp=
unordered_map<int, vector<int>> next;
unordered_set<int> inPath;
bool hasCyclic(int node)
{
// 碰到已經訪問過的node，有cyclic
if(inPath.count(node)) return true;
inPath.insert(node); // 紀錄訪問過的node
for(auto& n : next[node])
if(hasCyclic(n)) return true;
inPath.erase(node); // 刪除訪問過的node，往下一個path
return false;
}
```
3. 紀錄訪問過的node。例如一個path 0->2->3->4已經訪問過且確認沒cyclic，如果有也已經返回了。node 1接下來訪問node 2，因為node 2已經訪問過且沒cyclic所以就不需要再一次訪問。
```cpp=
unordered_set<int> v;
bool hasCyclic(int node)
{
if(inPath.count(node)) return true;
if(v.count(node)) return false; // 已經訪問過不會有cyclic
// 加入已經訪問過的node，雖然不確定會不會有cyclic
// 如果有，最後還是會返回true。
// 所以可以安心加入
v.insert(node);
inPath.insert(node);
for(auto& n : next[node])
if(hasCyclic(n)) return true;
inPath.erase(node);
return false;
}
```
+ [207. Course Schedule](/Rs3M7lf1TzOR0Lx_RhgpNg#207-Course-Schedule)
## BFS
使用queue來一層一層尋找答案
```cpp
queue<pair<int, int>> q;
while(!q.empty()) {
for(int i = q.size(); i > 0; --i) {
auto& p = q.front(); q.pop();
// 檢查接下來的node是否inRange且符合條件
// ** 把node做上記號避免之後重複尋找 ** //
// 將新的可能的node推進queue
q.push(newnode);
}
// update answer
}
```
例如 [1091. Shortest Path in Binary Matrix](/Rs3M7lf1TzOR0Lx_RhgpNg?both#1091-Shortest-Path-in-Binary-MatrixMedium)
除了使用queue，也可以使用priority_queue。使用priority_queue的目的是想更快的接近答案，因為每次選都是從最有可能的答案來處理。
例如 [1066. Campus Bikes II](https://leetcode.com/problems/campus-bikes-ii/description/)
```cpp=
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
while(!pq.empty()) {
auto [dist, mask] = pq.top(); pq.pop();
//條件成立，直接返回
int nextWorker = __builtin_popcount(mask);
if(nextWorker == workers.size()) return dist;
// 否則根據目前的條件，找尋下一個可能
for(int nextBike = 0; nextBike < bikes.size(); ++nextBike) {
if((mask &(1<< nextBike)) == 0) {
int nextDist = dist + getDist(workers[nextWorker], bikes[nextBike]);
int nextMask |= 1 << nextBike;
pq.push({nextDist, nextMask});
}
}
}
```
## Problems
### [565. Array Nesting(Medium)](https://leetcode.com/problems/array-nesting/)
依題意找出最大的集合。
```cpp=
int arrayNesting(vector<int>& nums) {
auto n = nums.size();
vector<bool> visited(n, false);
int cnt, rtn{0};
for(int start = 0; start < n; start++) {
if(visited[start]) continue;
cnt = 0;
int tmp = start;
while(!visited[tmp]) {
cnt++;
visited[tmp] = true;
tmp = nums[tmp];
}
rtn = max(rtn, cnt);
}
return rtn;
}
```
這邊需要一個額外的空間visited來存放是否訪問過，因為數字從0開始且不會重複，所以可以把數字放到和index相同的地方，就不用額外空間。
```cpp=
while (nums[i] != i) {
swap(nums[i], nums[nums[i]]);
++cnt;
}
```
### [733. Flood Fill(Easy)](https://leetcode.com/problems/flood-fill/)
給定一個起始點，把和起始點一樣數值的相鄰點塗成新的顏色。
> 這邊的重點是離開function的條件
> 1. 座標超出範圍
> 2. 已經走過
> 3. 數值和一開始的點不一樣
```cpp=
class Solution {
int n, m, orig, nc;
vector<vector<bool>> visited;
public:
void helper(vector<vector<int>>& image, int y, int x) {
if(x < 0 || y < 0 || y >= n || x >= m || visited[y][x] || image[y][x] != orig) return;
vector<pair<int, int>> steps = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
image[y][x] = nc;
visited[y][x] = true;
for(auto step : steps) {
int newx = x + step.second;
int newy = y + step.first;
helper(image, newy, newx);
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
n = image.size();
m = image[0].size();
orig = image[sr][sc];
nc = newColor;
visited = vector<vector<bool>>(n, vector<bool>(m, false));
helper(image, sr, sc);
return image;
}
};
```
### [542. 01 Matrix(Medium)](https://leetcode.com/problems/01-matrix/)
輸出一個矩陣，標示出和0的最短距離。
> 因為要找出距離0的最短距離，所以一開始先把0標註出來。
> 然後用queue把標註過的座標存起來，因為要從0開始往外擴散。
```cpp=
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 0) q.push({i, j});
else mat[i][j] = INT_MAX;
}
}
while (!q.empty()) {
auto t = q.front(); q.pop();
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || mat[x][y] <= mat[t.first][t.second] + 1) continue;
mat[x][y] = mat[t.first][t.second] + 1;
q.push({x, y});
}
}
return mat;
}
```
另外一個重點是，因為是找最短距離。所以目標值max[x][y]小於mat[t.first][t.second] + 1也可以不用繼續比。
```cpp=
mat[x][y] <= mat[t.first][t.second] + 1
```
### [994. Rotting Oranges(Medium)](https://leetcode.com/problems/rotting-oranges/)
腐爛的橘子會繼續讓旁邊的橘子腐爛，幾回合後橘子會全部腐爛，如果還有新鮮的橘子就會傳-1。
這一題和[01 Matrix](https://hackmd.io/Rs3M7lf1TzOR0Lx_RhgpNg?view#542-01-MatrixMedium)類似，但是這邊是要算出幾回合後會全部腐爛。所以這邊用res紀錄，==每處理過一次queue就++res==。
```cpp=
while (!q.empty() && freshLeft > 0) {
for (int i = q.size(); i > 0; --i) {
......
}
++res;
}
```
用一個queue放腐爛橘子的位置。
```cpp=
queue<vector<int>> q;
```
這邊有個特別的技巧，避免使用兩個queue。因為必須知道何時處理完queue，所以==在迴圈的一開始先記錄queue的大小==，之後再開始處理。
```cpp=
for (int i = q.size(); i > 0; --i) { ... }
```
另外，必須知道最後還有沒有新鮮的橘子，所以多了一個freshLeft來記錄。最後的程式碼如下:
```cpp=
int orangesRotting(vector<vector<int>>& grid) {
int res = 0, m = grid.size(), n = grid[0].size(), freshLeft = 0;
queue<vector<int>> q;
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) ++freshLeft;
else if (grid[i][j] == 2) q.push({i, j});
}
}
while (!q.empty() && freshLeft > 0) {
for (int i = q.size(); i > 0; --i) {
auto cur = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int x = cur[0] + dirs[k][0], y = cur[1] + dirs[k][1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1) continue;
grid[x][y] = 2;
q.push({x, y});
--freshLeft;
}
}
++res;
}
return freshLeft > 0 ? -1 : res;
}
```
### [863. All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/)
在binary tree中，給你一個TreeNode *target，找出離target距離k的TreeNode。
> 1. 如果這題是n-ary tree而且target是root的話，就是用BFS就可以完成。
> 2. 如何把binary tree轉成 n-ary tree?
> 3. 使用一個unordered_map<TreeNode *, vector<TreeNode *>> 來記錄每個node可以到達的parent和child，即可以達到n-ary tree的效果。
> 4. 最後再用BFS來選出距離為k的TreeNode。
```cpp
class Solution {
void helper(TreeNode *root, unordered_map<TreeNode *, vector<TreeNode *>>& m) {
if(root->left) {
m[root].push_back(root->left);
m[root->left].push_back(root);
helper(root->left, m);
}
if(root->right) {
m[root].push_back(root->right);
m[root->right].push_back(root);
helper(root->right, m);
}
}
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
// special case : k == 0, 不需要尋找。
if(k == 0) return {target->val};
// 建立map來記錄每個TreeNode可以訪問的node，包括parent和child
unordered_map<TreeNode *, vector<TreeNode *>> m;
helper(root, m);
// 因為target是pointer所以不用找，直接把target push到queue裡面。
queue<TreeNode *> q;
q.push(target);
// 使用visited避免重複訪問TreeNode
unordered_set<TreeNode *> visited;
visited.insert(target);
// 如果queue有東西且k還沒到0
while(!q.empty() && k != 0) {
k--;
for(int i = q.size(); i > 0; --i) {
TreeNode *p = q.front(); q.pop();
visited.insert(p);
for(auto& n : m[p]) {
if(!visited.count(n))
q.push(n);
}
}
}
// output
if(k != 0) return {};
vector<int> rtn;
while(!q.empty()) {
rtn.push_back(q.front()->val);
q.pop();
}
return rtn;
}
};
```
### [110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)
```cpp
class Solution {
// bottom up solution
int heigh(TreeNode *root) {
if(!root) return 0;
// 因為先呼叫自己，所以會先找到最後一個node
int l = heigh(root->left);
int r = heigh(root->right);
// 先判斷是否為-1，都不是才比較兩邊的差
if(l == -1 || r == -1 || abs(l - r) > 1) return -1;
return max(l, r) + 1;
}
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
return heigh(root) != -1;
}
};
```
### [1091. Shortest Path in Binary Matrix(Medium)](https://leetcode.com/problems/shortest-path-in-binary-matrix/)
找出從(0, 0)->(n-1, n-1)的最短路徑。
```cpp
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
if(grid[0][0]) return -1;
int n = grid.size();
vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
queue<vector<int>> q;
q.push({0, 0});
grid[0][0] = 1;
int dist = 1;
while(!q.empty()) {
for(int i = q.size(); i > 0; --i) {
int y = q.front()[0];
int x = q.front()[1];
q.pop();
if(y == n - 1 && x == n - 1) return dist;
for(auto& d : dirs) {
int newy = y + d[0];
int newx = x + d[1];
if(newy < 0 || newx < 0
|| newy == n || newx == n
|| grid[newy][newx]) continue;
// 先做上記號，避免之後重複尋找
grid[newy][newx] = 1;
q.push({newy, newx});
}
}
dist++;
}
return -1;
}
```
### [207. Course Schedule](https://leetcode.com/problems/course-schedule/description/)
```cpp=
class Solution {
vector<vector<int>> adj;
vector<int> v, inPath;
bool hasCyclic(int node) {
if(inPath[node]) return true;
if(v[node]) return false;
v[node] = 1; // 訪問過的node
inPath[node] = 1;
for(auto& n : adj[node]) {
if(hasCyclic(n)) return true; // 訪問過的node有cyclic就會return true
}
inPath[node] = 0;
return false;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
adj.resize(numCourses, vector<int>());
v.resize(numCourses);
inPath.resize(numCourses);
for(auto& r : prerequisites)
adj[r[1]].push_back(r[0]);
for(int i = 0; i < numCourses; ++i)
if(hasCyclic(i)) return false;
return true;
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
