Breadth-first Search （BFS)
690 Employee Importance
This could be done either in DFS or BFS traversal of the graph.
Both need a define a map to save the id to employee object pointer, so that we could easily get the
subordinate employee info while traversing.
For BFS, we use a deque<Employee*> since it is a super version of queue allowing us insert at both
end of the queue.
(1) push_back the mp[id] info into the queue
(2) while the queue is not empty, do the following:
pop_front the front element in the queue, add its importance to the the total importance of the employee id (either itself or its mangers'), push_back all its subordinate employee into the deque.
(3) return the total importance in the end.
Tree
This could be done either in DFS or BFS traversal of the graph.
Both need a define a map to save the id to employee object pointer, so that we could easily get the
subordinate employee info while traversing.
For BFS, we use a deque<Employee*> since it is a super version of queue allowing us insert at both
end of the queue.
(1) push_back the mp[id] info into the queue
(2) while the queue is not empty, do the following:
pop_front the front element in the queue, add its importance to the the total importance of the employee id (either itself or its mangers'), push_back all its subordinate employee into the deque.
(3) return the total importance in the end.
Tree
107 Binary Tree Level Order Traversal II
BFS: Define a queue (you could also use deque), push root in queue. loop each element while q is not empty, define a nextLevelStarter to keep track of the beginning node of each level. Loop the level for that level while q is not empty and nextLevelStarter is not equal the front element in queue. Update nextLevelStarter with either p->left or p->right if it is nullptr. Push non-empty left node and right node into the queue. When exit the inner loop, push the nodes in the current level into result. Also instead of using nextLevelStarter, you could get elements in each level by keep the number of elements (say size) in that level, and only loop size times. Both are O(N) time and O(N) space. 101 Symmetric Tree (1) BFS Two queues Define two queues left queue: lq and right queue rq. If the root is nullptr, return true. Otherwise, if root->left is not nullptr, lq.push(root->left), if root->right is not nullptr rq.push(root->right). While the two queues are both not nullptr do the following: Pop the two front element in both queues, say lf, and rf. And check whether their val is equal, if not cannot be symmetric tree, early return. Otherwise, check whether lf->left and rf->right is both not nullptr, if so push lf->left into the left queue and rf->right into the right queue. If both lf->left and rf->right are nullptr do nothing (so we can process lf->right and rf->left by falling through). If one of both lf->left and rf->right is nullptr cannot be symmetric, return false. Similarly for lf->right and rf->left. In the end check whether both queues are empty, if so return true, else return false. (2) BFS One stack Define one stack : stk. If the root is nullptr, return true. Otherwise, stk.push(root->left), stk.push(root->right). While stk is not empty() do the following: Pop the two front element from top of the stack, save it to s and t. If both s and t are both nullptr, continue If one of s or t is nullptr, return false Otherwise, both are not nullptr, if s->val != t->val, return false. Otherwise, push s->left, t->right, s->right, t->left onto the stack in order. In the end, if no early return, meaning the tree is symmetric. 111 Minimum Depth of Binary Tree (1) DFS if (!root) return 0; if (!root->left) return minDepth(root->right) + 1; if (!root->right) return minDepth(root->left) + 1; Otherwise: return min(minDepth(root->left), minDepth(root->right)) + 1; (2) BFS, use the similar way in 107 Binary Tree Level Order Traversal II to do BFS traversal, and return the minimum depth when see the first leaf (i.e: see a node with both children are nullptr).
(1) DFS. (pre,in,post order). pass reference of leftVal and maxDepth. And pass value of current depth, and the root. When (depth > maxDepth) update the {maxDepth = depth and leftVal = root->val }. Recursively call DFS(root->left, leftVal, depth + 1, maxDepth) and DFS(root->right, leftVal, depth + 1, maxDepth) (2) BFS again same idea with 111, 107, update the result value with the first element in each level. In the end it will has the left bottom value in the tree.
BFS: Same with 102, instead of keep all values, just keep the max value while level traversal. DFS: pass over the vector<int>& res array and depth, when res.size() == depth, push root->val into res. Otherwise when res.size() > depth, res[depth] = max(res[depth], root->val).
in the end. DFS: pass over the vector<int>& res array and depth, when res.size() == depth, push root->val into res. Otherwise when res.size() > depth, res[depth] = root->val. Keep updating the res[depth], which will contain the right most value in the end. Must use pre-order traversal to push back the res[depth] first and update it later. We can see that 102,199,513,515,107,111 are all have similar BFS solution, the DFS solution is slightly different, but still close. 103 Binary Tree Zigzag Level Order Traversal Stack solution 1: Use two stacks curLevel stack and nextLevel stack to traverse the tree. Since we need to output the nodes in normal order for odd level and reverse order for even level, we only need a bool flag (like zigzag). (1) Push the root into the curLevel stack before the loop. (2) while curLevel is not empty, repeat the following. (2.1) Define nextLevel stack, and level vector array to save this level nodes value (2.2) while curLevel is not empty() pop the top element. Depends on whether zigzag is true or false do the following: true : push the left and then push the right false: push the right and then push the left (2.3) flip zigZag flag, push the level to the result vector of vector array copy the nextLevel stack to the curLevel stack to do the next loop (go to (2)) Queue solution 2: Just like 102, 199, above. do the normal level traversal to collect all the nodes into a two dimension res array. Then reverse all the zag rows and leave zig rows as they are. Return the result. deque solution 3: Use the same level traversal architecture. But this time use deque to save the result. For zig rows do: pop back, push front, left then right. And for zag rows do: pop front, push back, right then left. 200. Number of Islands DFS: Double for loop to iterate each element in the matrix if it is equal to char '1' then increase counter and call DFSMark to set the current grid to '0' and recursively call DFSMark to set all the horizontally and vertically connect grids that have value '1' to '0' (i.e.: count only 1 time for all the connect grids, for one island). In the end counter has the number of the islands. BFS: The wrapper function is the same, but the helper function is different. Instead of call DFSMark recursively without loop. We can call BFSMark once and inside it we use a while loop to loop all the BFS neighbors with the help of a queue. For the BFS helper function. We create a queue and make_pair(row, col) and push it in the queue. while the queue is empty. Do the following: (1) Pop front and get the row and col from the front element. If it is out of range or it is not '1', continue. (2) Otherwise, push all its four neighbors up,down,left,right in the queue. Second time =========================================
Like Surrounded Regions, We could do BFS or DFS search from the board flow and marked all their adjacent flow which has a bigger or equal height to be visitable from Pacific or Atlantic. Then in the end we could for loop both the Pacific and Atlantic visited flags to push these flow position that are visitable from both Pacific and Atlantic to the result array and return it. 529 Minesweeper DFS: (a) the click is on the mine, explode and done. Otherwise: (b) Search 8 adjacent cells to count how many adjacent mines the current cell(x, y) has: (b.1) if there is at least 1 adjacent mines, then set the cell to the number of adjacent mines (b.2) Otherwise, there is no adjacent mine, then set the cell to Blank and recursively (DFS) reveal the 8 adjacent cells. BFS: Similar with DFS, except in the step (b.2) push its breadth first neighbor into the queue for next loop. 542. 01 Matrix Push all the 0 value coordinates in the matrix into the queue as the BFS start points. While the queue is not empty. Get the queue front element and explode the 4 direction for it to check whether there is a distance that has value greater than current element value plus 1, if so update it with current element value plus 1 and push that element into the queue to be used as a new start point for updating its neighbors. After updating all the neighbor distance in the queue, return the distance matrix as the result. Graph 863 All Nodes Distance K in Binary Tree Use DFS to build the graph, and use BFS to find and collect all the nodes that are exact K steps from target. 752 Open the Lock (1) Copy the deadends input string into a set to make it easy for find in the set (O(1) time) and also define a visited set to save the nodes already visited.
(2) Define a queue to do BFS in the visit graph. If initially the deadends set contains "0000" return -1. Otherwise push "0000" into the queue as the BFS starting point and also put it in the visited set.
(3) While the queue is not empty do the following:
(4) get the size of the queue and save it to a tmp variable say: size and loop the first size element in the queue and decrease it by 1 repeat the following, after visiting one element in the current level
(5) Pop the front element from the queue. Get all its 8 neighbor nodes (2 * 4 , one larger one smaller and 4 digits altogether ). For loop all the 8 neighbor nodes, if anyone is the target result, return ++ res. Otherwise, if it is already in the visited set, continue the next node. Otherwise if it is in the deadends set also continue. Otherwise, if none of the above push the neighbor node into the queue and add it to the visited set as well.
(6) In the end, if no early exit, meaning unreachable, return -1.
// O(8^20) time and space worst case [since each digit is reachable in 5 steps, have 4 digits all together] 743 Network Delay Time O(N*E) time O(N) space. Bellman Ford single source shortest path algorithm. (1) Repeat the following step 2 n times. (2) For loop each edge in the graph, get its source u and destination v, and weight w. If the distance from k to u plus w is less than the distance from k to v, update dist(v) = dist(u) + w. (3) For loop each distance in the distant array get the max value, which will be the wait time to propagate the message to each node in the graph. Could Use priority queue as well. 787 Cheapest Flights Within K Stops Bellman-Ford algorithm Similar to 743, except that we only need to iterate K + 1 time before stop. We also cannot do the update on the fly. Since we may update to much and get the value should be update in the next iteration. Therefore we have to save the price to a buff and update the buff value within the same inner loop. After the inner loop, we can copy the buff value to the price value and do the next iteration. BFS: (1) Construct a graph (2) Use a queue to do BFS search (only iterate K + 1 steps and exit). int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { unordered_map<int, vector<pair<int, int> > > graph; for (const auto& flight : flights) graph[flight[0]].emplace_back(flight[1], flight[2]); int res = INT_MAX; queue<pair<int, int> > q; q.push({src, 0}); int steps = 0; while (!q.empty()) { int size = q.size(); while (size--) { auto cur = q.front(); q.pop(); if (cur.first == dst) res = min(res, cur.second); for (const auto& neighbor : graph[cur.first]) { if (neighbor.second + cur.second > res) continue; q.push({neighbor.first, neighbor.second + cur.second}); } } if (steps++ > K) break; } return INT_MAX == res ? -1 : res; } 133. Clone Graph DFS: The main difficulty here is how to avoid repeated clone a GraphNode. We use hash map to record already cloned Nodes. In my understanding the question assume all the nodes are connected. Define a hash map from UndirectedGraphNode* to UndirectedGraphNode*. Base case: if node is nullptr, return nullptr if the node is not in the hash map yet. Clone the node and link the original node and the cloned node through hash map. For loop all the neighbors of the current node and recursively clone them and push_back them to the newly cloned node neighbor vector list. Otherwise, if the node is in the hash map, return the already cloned node. BFS: Use a queue and hash map to help do the breadth first search. Push the input node into the queue first. And then pop front element of the queue as current and for loop all the neighbors of current, if is not in the hash map yet. Clone the node push it into the queue add it to the already cloned hashMap[current]'s neighbor list. Return hashMap[node] in the end. 127 Word Ladder 这里用到了两个高级数据结构unordered_map和queue，即哈希表和队列，其中哈希表是记录单词和目前序列长度之间的映射，而队列的作用是保存每一个要展开的单词。首先把起始单词映射为1，把起始单词排入队列中，开始队列的循环，取出队首词，然后对其每个位置上的字符，用26个字母进行替换，如果此时和结尾单词相同了，就可以返回取出词在哈希表中的值加一。如果替换词在字典中存在但在哈希表中不存在，则将替换词排入队列中，并在哈希表中的值映射为之前取出词加一。如果循环完成则返回0 http://www.cnblogs.com/grandyang/p/4539768.html 207 Course Schedule DFS (Topological sorting): (1) make adjacent list to denote graph based on the input edges. (2) Initialize the state of all the course to unknown (0) (3) For loop all the courses and do dfs traversal with a dfs helper function if dfs found a cycle return false (meaning cannot schedule the courses). If no early exit, meaning can schedule the courses. For the DFS helper. If cur node is in visiting return true. if cur node is already visited and coming into the dfs again, a cycle has been detcted, return false. Otherwise, set it to the visiting state. DFS recursively visit its neighbors, if found a cycle return cycle. If after visiting all the neighbors and not cycles found, return OK (true), meaning no cycle found. 210 Course Schedule II Same algorithm with 207, except we have to save the cur course to the result array after DFS recursion and see it at the first time. In the end return the reversed order. BFS: (to do) 310 Minimum Height Trees One sentence : peeling the onion Peel off the leaf node layer by layer from outside until only one or two nodes left, which will be the MHT root. 785 Is Graph Bipartite? DFS: For loop all the vertexes in the graph, if not colored yet, call dfsGraphColoring to do the graph coloring starting with the current vertex, in which if able to color all the graph without adjacent nodes having same color, return true, otherwise return false. if dfsGraphColoring return false, meaning it is not a bipartite, early return. Otherwise after the loop, return true, meaning it is a bipartite. In dfsGraphColoring, we do the following: if already colored, return true if the previous colored color is the same with the current wanted color, else return false (meaning we want to color the same node with two different colors, it is impossible). If not colored yet, color it to the given color from the input parameter. For loop all the neighbors of the current node, try to coloring them with the opposite color, if not success, early return false. If all succeed, return true. // dfsGraphColoring(vector<vector<int>>& graph, vector<Color>& colors, Color color, int idx) BFS: Iterate all the vertexes, if not colored yet, color it to black. Iterately visit all the nodes using BFS, put the current vertex into the queue. While the queue is not empty, get the front element visit all its neighbor vertexes, if not colored yet, color it to the opposite color (black ? white : black). And then add its neighbors to the queue. Else if the current vertex current and its neighbor have the same color return false directly. After the while return true. |
Comments
Post a Comment