自己呼叫自己達到DFS的效果。可以分成兩種形式。
void dfs(node *root) {
// 先做運算
...
// 最後在呼叫自己
dfs(root->next);
}
void dfs(node *root) {
// 先呼叫自己，則會先走訪到最後node
dfs(root->next);
// 最後在做運算判斷
...
}
例如 110. Balanced Binary Tree 適合用bottom-top。
for(int i = 0; i < numNodes; ++i) {
if(hasCyclic(i)) return true;
}
return false;
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;
}
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;
}
使用queue來一層一層尋找答案
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
除了使用queue，也可以使用priority_queue。使用priority_queue的目的是想更快的接近答案，因為每次選都是從最有可能的答案來處理。
例如 1066. Campus Bikes II
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});
}
}
}
依題意找出最大的集合。
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相同的地方，就不用額外空間。
while (nums[i] != i) {
swap(nums[i], nums[nums[i]]);
++cnt;
}
給定一個起始點，把和起始點一樣數值的相鄰點塗成新的顏色。
這邊的重點是離開function的條件
- 座標超出範圍
- 已經走過
- 數值和一開始的點不一樣
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;
}
};
輸出一個矩陣，標示出和0的最短距離。
因為要找出距離0的最短距離，所以一開始先把0標註出來。
然後用queue把標註過的座標存起來，因為要從0開始往外擴散。
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也可以不用繼續比。
mat[x][y] <= mat[t.first][t.second] + 1
腐爛的橘子會繼續讓旁邊的橘子腐爛，幾回合後橘子會全部腐爛，如果還有新鮮的橘子就會傳-1。
這一題和01 Matrix類似，但是這邊是要算出幾回合後會全部腐爛。所以這邊用res紀錄，每處理過一次queue就++res。
while (!q.empty() && freshLeft > 0) {
for (int i = q.size(); i > 0; --i) {
......
}
++res;
}
用一個queue放腐爛橘子的位置。
queue<vector<int>> q;
這邊有個特別的技巧，避免使用兩個queue。因為必須知道何時處理完queue，所以在迴圈的一開始先記錄queue的大小，之後再開始處理。
for (int i = q.size(); i > 0; --i) { ... }
另外，必須知道最後還有沒有新鮮的橘子，所以多了一個freshLeft來記錄。最後的程式碼如下:
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;
}
在binary tree中，給你一個TreeNode *target，找出離target距離k的TreeNode。
- 如果這題是n-ary tree而且target是root的話，就是用BFS就可以完成。
- 如何把binary tree轉成 n-ary tree?
- 使用一個unordered_map<TreeNode *, vector<TreeNode *>> 來記錄每個node可以到達的parent和child，即可以達到n-ary tree的效果。
- 最後再用BFS來選出距離為k的TreeNode。
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;
}
};
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;
}
};
找出從(0, 0)->(n-1, n-1)的最短路徑。
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;
}
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;
}
};
leetcode 刷題
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe