Questions ========================================= Babyfaces And Heels ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There are 2 types of professional wrestlers: babyfaces and heels. Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Write a function to determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. For example: Given n = 5 and 5 pairs of wrestlers: {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {3, 4}}, return true. Given n = 5 and 5 pairs of wrestlers: {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {2, 3}}, return false. Is Graph A Valid Tree? ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}}, return true. Given n = 5 and edges = {{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}}, return false. .. walls_gates: Walls and Gates ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given a m x n 2D grid initialized with these three possible values. -1 - A wall or an obstacle. 0 - A gate. INF - Infinity means an empty room. We use the value 2^{31} - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF. For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 ---- This is a simple version of multi-source-BFS problem. It is simple because the graph is clear, which is made of all INF nodes, and you can mark it to a non-INF value so you don't have to maintain a visited set for nodes that has been traversed. This graph is changed when tracersing so that you can't go back to traverse the same node again. .. literalinclude:: bfs_walls_gates_test.cpp :linenos: :lines: 6-24 :language: c++ :emphasize-lines: 6-8,15-16 | line 6-8: put all sources into the queue, which is the frist layer of the BFS traversal | line 15-16: move to the next node in the BFS traversal and update the graph .. only:: html - http://leetcode.com/problems/walls-and-gates/ .. _word_ladder: Word Ladder ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example, given: beginWord = “hit”, endWord = “cog”, wordList = {“hot”,“dot”,“dog”,“lot”,“log”,“cog”}. As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5. Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. No duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. ---- .. literalinclude:: 127_Word_Ladder_test.cpp :linenos: :lines: 24-45 :language: c++ :emphasize-lines: 6-8 This solution is fast because: #. Bidirectional-BFS #. No graph building, just finding neighbours on the fly. #. No visited set, just reusing wordList and erasing visited node from it .. only:: html Another version which uses int in the unordered set. .. literalinclude:: 127_Word_Ladder_test.cpp :linenos: :lines: 48-83 :language: c++ :emphasize-lines: 20-34 .. only:: html - https://leetcode.com/problems/word-ladder/ Word Ladder II ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example, given: beginWord = “hit”, endWord = “cog” wordList = {“hot”,“dot”,“dog”,“lot”,“log”,“cog”} Return { {“hit”,“hot”,“dot”,“dog”,“cog”}, {“hit”,“hot”,“lot”,“log”,“cog”} } Note: Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. ---- There are two steps to solve this problem. First, Expression Add Operators ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value. Examples: "123", 6 -> {"1+2+3", "1*2*3"} "232", 8 -> {"2*3+2", "2+3*2"} "105", 5 -> {"1*0+5","10-5"} "00", 0 -> {"0+0", "0-0", "0*0"} "3456237490", 9191 -> {} Course Schedule ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: {0,1} Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, {{1,0}} There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, {{1,0},{0,1}} There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible. Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites. Hints: 1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses. 2. There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate? 3. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. 4. Topological sort could also be done via BFS. ---- The question reminds me of my college life. When choosing a course, we often encounter that we want to choose a certain course, but find out which courses must be taken before choosing it. This question gives a lot of hints, The first one tells that the essence of this problem is to detect cycles in a directed graph. The second hint is about how to represent a directed graph, which can be represented by an edge, and an edge is represented by two points. The third and fourth hints reveal that there are two solutions to this problem, both DFS and BFS can solve this problem. Let's first look at the solution of BFS. - BFS .. literalinclude:: course_schedule_test.cpp :linenos: :lines: 34-57 :language: c++ :emphasize-lines: 13, 4-5 :name: course_schedule_bfs :caption: Course Schedule BFS In :numref:`course_schedule_bfs`, we first define a two-dimensional vector `graph` to represent this directed graph, and a one-dimensional vector `in` to represent the in-degree of each vertex. Then we start to build this directed graph based on the input, and initialize the in-degree array as well. Then define a queue variable, put all the points whose in-degree is 0 into the queue, and then start looping through the queue. For each vertex popped out from the queue, we decrease the in-degree of the connected vertex in the graph by 1. If the connected vertex's in-degree becomes 0, it is enqueued at the end of the queue. When all the vertices ​​in the queue are popped out, if there is still any non-zero in-degree vertex in the graph, it means that circle exists and then we returns false. Otherwise, we returns true. topologically sortable == No cycle! - Kahn Algorithm Kahn's algorithm is a more generic solution based on BFS. We need a successor graph and a predecessor graph, and a set with all vertices. Note we've never used numCourses in the function in :numref:`course_schedule_kahn`. .. literalinclude:: course_schedule_test.cpp :linenos: :lines: 6-32 :language: c++ :emphasize-lines: 13, 4-5 :name: course_schedule_kahn :caption: Course Schedule Kahn BFS #. Find 0-indegree node: delete the key of pre from ns, ns==[a], which contains 0-indegree nodes('a' in this case). #. Then remove all a nodes from pre and suc : First check suc, look for points b, c, f in suc[a], then look for pre[b], pre[c], pre[f], which must all contain a, delete this a, if there is any left The next is an empty set, indicating that another 0-indegree node is found. #. Repeat until ns is empty! #. Finally, if pre and suc are also empty, it means that it is topologically sortable!!! In this process, all the nodes have been found in order. node, in another words, we have done topological sort. - Postorder DFS Let's look at the solution of DFS. We also need to build a directed graph using a two-dimensional vector. Unlike BFS, a one-dimensional vector `visit` is used to track the vertex state. A vertex has three states in DFS: 0 means ``undiscovered``, 1 means ``finished``, -1 means ``discovered``. The basic idea is to build a directed graph first, then start from the first course, find which course we can take after the first course, temporarily mark the current course as `discovered`, and then call DFS recursively on the newly obtained course. If a new course has status `discovered`, return false because discovering a course two times means a circle is detected. If it has status `finished`, return true. .. literalinclude:: course_schedule_test.cpp :linenos: :lines: 59-79 :language: c++ :emphasize-lines: 13, 4-5 :name: course_schedule_dfs :caption: Course Schedule DFS - Complexity | Time Complexity: O(∣E∣+∣V∣) where ∣V∣ is the number of vertices, and ∣E∣ is the number of edges. | Space Complexity: O(∣E∣+∣V∣). .. only:: html - https://leetcode.com/problems/course-schedule/ - http://www.cnblogs.com/grandyang/p/4484571.html - https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm - (CLRS p615. 22.4-3) Course Schedule II ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: {0,1} Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array. Example: Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3]. ---- .. literalinclude:: course_schedule_test.cpp :linenos: :lines: 81-99 :language: c++ :emphasize-lines: 13, 4-5 :name: course_schedule_bfs :caption: Course Schedule 2 BFS |:alien:| follow up - find all feasible solutions: .. code-block:: c++ // Construct predecessor subgraph and BFTree vector> r; while (!Q.empty()) { int count = Q.size(); vector p; while (--count) { int t = Q.front(); Q.pop(); p.push_back(t); for (int i : G[t]) { if (--in[i] == 0) Q.push(i); } } r.push_back(p); } // DFS to find all paths Refer to :numref:`phone_pad_seq`. .. only:: html - https://leetcode.com/problems/course-schedule-ii/ Reconstruct Itinerary ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given a list of airline tickets represented by pairs of departure and arrival airports {from, to}, reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary {“JFK”, “LGA”} has a smaller lexical order than {“JFK”, “LGB”}. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: tickets = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}} Return {"JFK", "MUC", "LHR", "SFO", "SJC"}. Example 2: tickets = {{"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}} Return {"JFK","ATL","JFK","SFO","ATL","SFO"}. Another possible reconstruction is {“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”}. But it is larger in lexical order. Note there may be more than one same tickets. For example: {{'ANU', 'EZE'}, {'ANU', 'JFK'}, {'ANU', 'TIA'}, {'AXA', 'TIA'}, {'EZE', 'AXA'}, {'JFK', 'ANU'}, {'JFK', 'TIA'}, {'TIA', 'ANU'}, {'TIA', 'ANU'}, {'TIA', 'JFK'}} .. only:: html - https://leetcode.com/problems/reconstruct-itinerary/ Alien Dictionary ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There is a new alien language that uses the lower-case English alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them. A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length. Example 1: Input: words = {"wrt","wrf","er","ett","rftt"} Output: "wertf" Example 2: Input: words = {"z","x"} Output: "zx" Example 3: Input: words = {"z","x","z"} Output: "" Explanation: The order is invalid, so return "". .. only:: html - https://leetcode.com/problems/alien-dictionary/ Is Graph Bipartite? ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given a graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B. The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice. The graph may not be connected. Example 1: Input: {{1,3}, {0,2}, {1,3}, {0,2}} Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}. Example 2: Input: {{1,2,3}, {0,2}, {0,1,3}, {0,2}} Output: false Explanation: The graph looks like this: 0----1 | \ | | \ | 3----2 We cannot find a way to divide the set of nodes into two independent ubsets. ---- The graph is given in adjacency list form with the vector index as the key. We can use another extra color vector to track the color of visited nodes, while it is also used as `visited` set to check if a node has been visited. - BFS color: 0 ==> unknown, 1 ==> black, -1 ==> red .. literalinclude:: is_bipartite.h :linenos: :lines: 48-68 :language: c++ :emphasize-lines: 13, 4-5 | line 4: check all nodes because the graph may not be connected. - DFS color: -1 ==> unknown, 0 ==> black, 1 ==> red .. literalinclude:: is_bipartite.h :linenos: :lines: 72-91 :language: c++ :emphasize-lines: 13 |:feet:| To generate alternate sequence, we can do ``1*-1*-1...`` or ``0^1^1^1...``. .. only:: html - https://leetcode.com/problems/is-graph-bipartite/ .. _cheapest_flight: Cheapest Flights Within K Stops ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w. Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1. Example: +---+ | 0 | +---+ / \ 100 500 / \ v v +---+ +---+ | 1 | ---100---> | 2 | +---+ +---+ Input: n = 3, edges = {{0,1,100},{1,2,100},{0,2,500}}, src = 0, dst = 2, k = 1; Output: 200 The cheapest price from city 0 to city 2 with at most 1 stop costs 200(0->1->2). Input: n = 3, edges = {{0,1,100},{1,2,100},{0,2,500}}, src = 0, dst = 2, k = 0; Output: 500 The cheapest price from city 0 to city 2 with at most 0 stop costs 500(0->2). ---- - Brute Force (DFS) .. literalinclude:: 787_best_price_with_stops_test.cpp :linenos: :lines: 96-117 :language: c++ :emphasize-lines: 12-21 :caption: DFS with TC: O(V^2*K) We can use `Memoization` to optimize the DFS algorithm. - Bellman Ford An important part to understanding the Bellman Ford's working is that at each step, the relaxations lead to the discovery of new shortest paths to nodes. After the first iteration over all the vertices, the algorithm finds out all the shortest paths from the source to nodes which can be reached with one hop (one edge). That makes sense because the only edges we'll be able to relax are the ones that are directly connected to the source as all the other nodes have shortest distances set to inf initially. Similarly, after the (K+1)th step, Bellman-Ford will find the shortest distances for all the nodes that can be reached from the source using a maximum of K stops. Isn't that what the question asks us to do? If we run Bellman-Ford for K+1 iterations, it will find out shortest paths of length K or less and it will find all such paths. We can then check if our destination node was reached or not and if it was, then the value for that node would be our shortest path! .. literalinclude:: 787_best_price_with_stops_test.cpp :linenos: :lines: 10-26 :language: c++ :emphasize-lines: 6-13 Line 6: To modify the unordered_map when looping through it, we need to make a copy first and then loop the copy. - Dijkstra As for Dijkstra, here we can't do relaxation, because if the smaller cost path has more than k stops it won't be valid! .. figure:: best_price.png :align: center :name: best_price Test cases for cheapest flights In :numref:`best_price`, case a and c will have result 400 and 6 respectively if there is no constraint of most k stops. .. literalinclude:: 787_best_price_with_stops_test.cpp :linenos: :lines: 29-44 :language: c++ :emphasize-lines: 4, 15 Reference: :numref:`beford`, :numref:`dijkstra_algo_main` .. only:: html - https://leetcode.com/problems/cheapest-flights-within-k-stops/ Lowest Price With Shopping Offers ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none In a store, there are some kinds of items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price. You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer. You could use any of special offers as many times as you want. Example 1: Input: {2,5}, {{3,0,5},{1,2,10}}, {3,2} Output: 14 Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively. In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay $10 for 1A and 2B. You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A. Example 2: Input: {2,3,4}, {{1,1,0,4},{2,2,1,9}}, {1,2,1} Output: 11 Explanation: The price of A is $2, and $3 for B, $4 for C. You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. You cannot add more items, though only $9 for 2A ,2B and 1C. Note: There are at most 6 kinds of items, 100 special offers. For each item, you need to buy at most 6 of them. You are not allowed to buy more items than you want, even if that would lower the overall price. .. only:: html https://leetcode.com/problems/shopping-offers Valid Path With Landmark ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. figure:: gg_landmark_path.png :align: center .. code-block:: none N cities from 1 to N, each city has either landmark A or B. Return true if there is a path from x to y so that path has the specified landmark, otherwise return false Example: Landmarks: 1:a,2:b,3:b,4:a,5:a Paths: 1-2, 1-5, 3-4, 3-5, 4-5 input: (1, 4, a); output: true from 1 to 4, there are two paths: 1=>5=>4 is not valid because there is no landmark b in the path. However, there is another pat 1=>5=>3=>4, which has b in it, so return true. ---- To return true, there are two conditions: path exists, and the path contains at least one specific landmark. .. literalinclude:: gg_landmark_path_test.cpp :linenos: :lines: 10-38 :language: c++ :emphasize-lines: 18-20 Minimum Height Trees ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels. Format: The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels). You can assume that no duplicate edges will appear in edges. Since all edges are undirected, {0, 1} is the same as {1, 0} and thus will not appear together in edges. Example 1: Given n = 4, edges = {{1, 0}, {1, 2}, {1, 3}}, return {1}. 0 | 1 / \ 2 3 Example 2: Given n = 6, edges = {{0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}}, return {3, 4}. 0 1 2 \ | / 3 | 4 | 5 ---- This question is about an undirected graph. And it is also a tree, so there is no circle! So using Khan Algo's idea is like to peel an onion! But when will it be peeled? Because there is no circle, so to It ends when there are only 2 or 1 node left. How to determine the outermost leaf node? We should check if degree(undirected graph) or in-degree(DAG) is one. .. literalinclude:: mhtree_test.cpp :linenos: :lines: 6-32 :language: c++ :emphasize-lines: 8-13,16-21 The implementation of this solution involves how to delete elements from the STL container in a loop, one of the bug-prone areas. .. only:: html https://leetcode.com/problems/minimum-height-trees Reconstruct Graph With Parent Nodes When Peeling Nodes ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Given an undirected tree, also a graph, delete a leaf node on the graph each time, and put the adjacent node(s) connected to the leaf node into an array, until there are only two nodes in the graph. When there are multiple leaves to delete, start from the minimum numbered node. The problem is that given this array, reconstruct the structure of the graph. Function signature is: vector> reconstruct_tree(int n, vector); N = 7 mean a tree with 7 nodes tagged from 1 to 7. The node removal algorithm goes as follows: 1. original tree 1-----5-----6------7-----4 {} | | 2 3 2. delete 1 and add 5 5-----6------7-----4 {5} | | 2 3 3. delete 2 and add 5 5-----6------7-----4 {5,5} | 3 4. delete 3 and add 6 5-----6------7-----4 {5,5,6} 5. delete 4 and add 7 5-----6------7 {5,5,6,7} 6. delete 5 and add 6 6------7 {5,5,6,7,6} 7. stop The calling reconstruct_tree(7, {5,5,6,7,6}) should reconstruct the original tree. Another example: calling reconstruct_tree(4, {2,2}) will reconstruct the following tree {{2,1},{3,2},{4,2}}: 1 | 2 / \ 3 4 ---- The elements in the input list start out as parents, and at some point they become leaves. Two steps: 1. Find the initial leaf node (the outermost leaf) and connect the outermost leaf to their parent. 2. The key is how to find the inner leaf node. You can use a counter to count the elements in the input list. Each time an element is connected to a leaf, the counter is reduced by 1. When the counter is 0, it means that the parent has become a new leaf, add it to leaf sets. Until I have seen all the elements in the input list, there are still two points in the leaf sets, which are the two innermost nodes. .. literalinclude:: gg_reconstruct_tree_test.cpp :linenos: :lines: 7-34 :language: c++ :emphasize-lines: 8-13,16-21 .. only:: html - https://www.1point3acres.com/bbs/thread-871556-1-1.html Shortest Path in a Grid with Obstacles Elimination ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. Example 1: j---> > > 0 1 2 +---+---+---+ i 0 | | | | | +---+---+---+ v 1 | x | x | x | v +---+---+---+ v 2 | | x | | +---+---+---+ Input: grid = {{0,0,0},{1,1,1},{0,1,0}}, k = 1 Output: 4 Explanation: The shortest path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). Example 2: j---> > > 0 1 2 +---+---+---+ i 0 | | | x | | +---+---+---+ v 1 | x | x | x | v +---+---+---+ v 2 | x | x | | +---+---+---+ Input: grid = {{0,0,1},{1,1,1},{1,1,0}}, k = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk. ---- In regular BFS, each node in the graph is denoted as the position {x, y} in the grid. But in this question, we also want to track how many obstacles we have destroyed so far. .. code-block:: none :caption: Example 1 steps obstacles 0 1 2 0 1 2 +---+---+---+ +---+---+---+ 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | +---+---+---+ +---+---+---+ 1 | 1 | 2 | 3 | 1 | 1 | 1 | 1 | +---+---+---+ +---+---+---+ 2 | 2 | 3 | 4 | 2 | 1 | 2 | 1 | +---+---+---+ +---+---+---+ .. code-block:: none :caption: Example 2 steps obstacles 0 1 2 0 1 2 +---+---+---+ +---+---+---+ 0 | 0 | 1 | 2 | 0 | 0 | 0 | 1 | +---+---+---+ +---+---+---+ 1 | 1 | 2 | 3 | 1 | 1 | 1 | 2 | +---+---+---+ +---+---+---+ 2 | 2 | 3 | 4 | 2 | 2 | 2 | 2 | +---+---+---+ +---+---+---+ This question is just two steps more than regular medium BFS question. All we need to do is to add one demension to track the visit path and one more variable(co - count of obstacles) to track how many obstacles we have encountered. Once we get those two things sorted out, we can easily code up the solution with regular "BFS formula". .. literalinclude:: gg_shortest-path-with-obstacles-elimination_test.cpp :linenos: :lines: 5-31 :language: c++ .. only:: html - https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ Wall In Gird World ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none A 2D array in which 0 is an open space and 1 is a wall. If you can remove at most one wall, can you reach the lower right cell from the upper left cell? Example: {0, 0, 0, 1, 0, 0} {-, -, -, 1, 0, 0} {1, 1, 0, 1, 0, 0} {1, 1, -, 1, 0, 0} {0, 0, 0, 0, 0, 0} --> {0, 0, -, -, -, -} {1, 1, 1, 1, 1, 1} {1, 1, 1, 1, 1, -} {0, 0, 0, 0, 1, 0} {0, 0, 0, 0, 1, -} The answer is true for the above example and the possible path is marked as `-`. Follow up: to reach the bottom right cell, at least how many walls you need to remove? Example: {0, 1, 0, 1, 0, 1} {-, 1, 0, 1, 0, 1} {1, 1, 0, 1, 0, 0} {-, 1, 0, 1, 0, 0} {0, 0, 0, 1, 1, 0} --> {-, 0, 0, 1, 1, 0} {1, 1, 1, 1, 1, 1} {-, 1, 1, 1, 1, 1} {0, 0, 0, 0, 1, 0} {-, -, -, -, -, -} One possible path is marked as `-` above. The walls to remove number is 3. ---- .. literalinclude:: gg_grid_with_wall_test.cpp :linenos: :lines: 6-26 :language: c++ The following is the number-of-walls-removed matrix. .. code-block:: none 0 1 1 2 2 3 1 2 1 2 2 2 1 1 1 2 3 2 2 2 2 3 4 3 2 2 2 2 3 3 8-Puzzle ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The 8-puzzle problem is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board position (left) to the goal position (right). .. code-block:: none 1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 initial goal Solution: **Best-First Search**. We now describe an algorithmic solution to the problem that illustrates a general artificial intelligence methodology known as the `A\* Search `_ algorithm. We define a state of the game to be the board position, the number of moves made to reach the board position, and the previous state. First, insert the initial state (the initial board, 0 moves, and a null previous state) into a priority queue. Then, delete from the priority queue the state with the minimum priority, and insert onto the priority queue all neighboring states (those that can be reached in one move). Repeat this procedure until the state dequeued is the goal state. The success of this approach hinges on the choice of priority function for a state. We consider two priority functions: Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intutively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that have been reached using a small number of moves. Manhattan priority function. The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state. For example, the Hamming and Manhattan priorities of the initial state below are 5 and 10, respectively. .. code-block:: none 8 1 3 1 2 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 4 2 4 5 6 ---------------------- ---------------------- 7 6 5 7 8 1 1 0 0 1 1 0 1 1 2 0 0 2 2 0 3 initial goal Hamming = 5 + 0 Manhattan = 10 + 0 We make a key oberservation: to solve the puzzle from a given state on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank tile when computing the Hamming or Manhattan priorities.) Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves from the initial board to the board associated with the state, but one that makes the fewest number of moves. (Challenge for the mathematically inclined: prove this fact.) .. literalinclude:: 8puzzle_AStar.h :linenos: :lines: 106-126 :language: c++ :emphasize-lines: 6-8,15-16 .. literalinclude:: 8puzzle_AStar.h :linenos: :lines: 22-51 :language: c++ Magic Squares ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ After inventing the globally popular Rubik's Cube, Mr. Rubik came up with its 2D version called the Rubik's Board. It consists of 8 equally-sized squares arranged as follows: .. code-block:: none 1 2 3 4 8 7 6 5 Each square of the Rubik's Board is colored. These 8 colors are represented by the first 8 positive integers. A sequence of colors can represent a state of the Rubik's Board. Starting from the top-left square and going clockwise, we form a color sequence. For example, the state depicted above is represented by the sequence 1,2,3,4,5,6,7,8. This is the basic state. Three basic operations are provided, denoted by uppercase letters A, B, and C (these operations can alter the state of the Rubik's Board): - A: Swap the top and bottom rows. - B: Move the rightmost column to the leftmost position. - C: Rotate the middle part of the board clockwise. Here are demonstrations of these operations on the basic state: .. code-block:: none A: 8 7 6 5 1 2 3 4 B: 4 1 2 3 5 8 7 6 C: 1 7 2 4 8 6 3 5 For each possible state, these three basic operations can be used. Your task is to program and compute *the minimum number of basic operations* required to transform the basic state into a specific state, and output *the sequence of basic operations*. .. code-block:: none Example Input: 2 6 8 4 5 7 3 1 Example Output: 7, BCABCCB We can use **BFS** to solve this question. .. literalinclude:: code/magic_squares_test.cpp :linenos: :lines: 37-57 :language: c++ :emphasize-lines: 44-55 Sort Matrix By Swap ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none :caption: Sort Matrix By Swap Given an NxN matrix with unique integer, find the sequence of swap to get a sorted matrix. Example: +---+---+---+ +---+---+---+ | 1 | 3 | 2 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ | 4 | 5 | 9 | => | 4 | 5 | 6 | +---+---+---+ +---+---+---+ | 7 | 8 | 6 | | 2 | 8 | 9 | +---+---+---+ +---+---+---+ The output is: [[2,3],[6,9]] ---- The solution is obviously A\*. Robot Car ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none A robot car starts at position 0 and speed +1 on an infinite number line. The car can go into negative positions. it car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse): When you get an instruction 'A', your car does the following: position += speed speed *= 2 When you get an instruction 'R', your car does the following: If your speed is positive then speed = -1 otherwise speed = 1 Your position stays the same. For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1. Given a target position target, return the length of the shortest sequence of instructions to get there. Example 1: Input: target = 3, Output: 2 Explanation: The shortest instruction sequence is "AA". Your position goes from 0 --> 1 --> 3. Example 2: Input: target = 6, Output: 5 Explanation: The shortest instruction sequence is "AAARA". Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6. ---- Since this is a shortest path question and we have only two choices `A` and `R`, we can use BFS. .. code-block:: none :caption: position tree 0 / \ 1 0 / \ 3 1 / \ 7 3 / \ 15 7 / \ 6 7 .. literalinclude:: code/robot_car_test.cpp :linenos: :lines: 7-29 :language: c++ .. only:: html - https://leetcode.com/problems/race-car/ Expression Add Operators ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value. .. code-block:: none Examples: "123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> [] .. only:: html - https://leetcode.com/problems/expression-add-operators/ Flight Route With Max Fun ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none There are n cities connected by some number of bi-directional flights and every city has a `fun value` measuring how fun this city is for a tourist. The fun values are additive. Return the maximum sum of fun values of a flight from a city to another city with exact 2 stops. If no such flight exists, return -1. Example: 1(2) / | \ 0(5)---|---2(9)---4(4) | / 3(8) Input: fun_value = [5,2,9,8,4], flights = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] Output: 24 (the flight will travel 0->1->2->3, and the total fun value is 5 + 2 + 9 + 8 = 24.) ---- Let's check the example above. The max-fun flight route, or the critical path, is 0->1->2->3. How can we get it? If we have edge between city 1 and city 2, and they both have many neighbors, the critical path must from two max-fun neighbours of 1 and 2 and they should not be the same. .. code-block:: none :caption: critical path \ / --1----2-- / \ .. code-block:: none :caption: The critical path must from two max-fun neighbours of 1 and 2 and they should not be the same \ / --1-----2-- \ / 3 .. code-block:: none :caption: the neighbors are sorted by fun values 1's neighbors: 2(9), 3(8), 0(5) 2's neighbors: 3(8), 0(5), 4(4), 1(2) .. code-block:: none :caption: find results in the two ordered neighbor lists it0 end0 1's neighbors: 2(9), 3(8), 0(5) it1 end1 2's neighbors: 3(8), 0(5), 4(4), 1(2) We can see the critical path could be 0->1->2->3 or 3->1->2->0. .. literalinclude:: code/max_fun_values_test.cpp :linenos: :language: c++ .. only:: html - https://www.1point3acres.com/bbs/thread-888288-1-1.html - https://www.youtube.com/watch?v=JYIh-mQJujs&ab_channel=ProgrammingLivewithLarry - https://leetcode.com/problems/maximum-score-of-a-node-sequence/discuss/1967776/Compute-top-3-neighbors-using-multimap-then-combine - https://leetcode.com/problems/maximum-score-of-a-node-sequence/discuss/1953681/C%2B%2B-O(E)-Try-every-edge-%2B-find-2-more-best-nodes-(one-per-each-edge-side) Create Recipes ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes. You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them. Return a list of all the recipes that you can create. You may return the answer in any order. Note that two recipes may contain each other in their ingredients. Example: Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". ---- This is a topological sort with BFS question. .. figure:: code/topo_recipes.png :align: center :name: graph_recipes Graph of Recipes and Ingredients We use Kahn's algorithm: .. code-block:: none bread(2)----> sandwich(2). bread(0)----> sandwich(1) sandwich(0) ^ ^ ^ / \ \ yeast(0) flour(0) meat(0) .. literalinclude:: code/topo_recipes_test.cpp :linenos: :lines: 4-100 :language: c++ .. only:: html - https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/ - https://leetcode-cn.com/problems/find-all-possible-recipes-from-given-supplies/solution/cong-gei-ding-yuan-cai-liao-zhong-zhao-d-d02i/ Network Delay Time ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. Example 1: (2)--1--> (1) \ \--1--> (3) --1--> (4) Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 Example 2: Input: times = [[1,2,1]], n = 2, k = 1 Output: 1 Example 3: Input: times = [[1,2,1]], n = 2, k = 2 Output: -1 .. only:: html - https://leetcode.com/problems/network-delay-time/solution/ City Traveler ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none Give a 2-d matrix, where each cell represents a city and each city has a traffic light. Initially all the light are red. At the beginning, the number of each cell represents the time when the red light turns green. When it turns to greeen, it means that you can leave the city. Red light indicates that you can't leave the city. You can travel in two directions: down and right. Return the shortest time you can travel from upper left to lower right city. Example input: {{1, 2, 0}, {4, 6, 5}, {9, 6, 5}} output: 5 ---- Solution: DP dp[i][j] = Min(dp[i-1][j],dp[i][j-1]) |:alien:| Follow up: travel in four directions: up, down, left, right .. code-block:: none {{1, 1, 1}, {K, K, 1}, {6, 6, 5}, {1, K, K}, {1, 1, 1}, {1, K, 5}} Dijkstra: cost(i1j1, i2j2) = grid[i1][j1] Count Lakes ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ A satellite image contains pixels tagged by letter 'x' and sign '.', where 'x' means land and '.' means water. The defition of lake is a water area all surrounded by lands. In the following sample image, for example, (8,a) is not a lake, but (4,c) and (4, d) form a lake. .. code-block:: none Sample Image: a b c d e f g h i j k l m n o p q 0 {., ., ., ., ., ., ., ., ., ., ., ., ., ., ., ., .} 1 {., ., ., ., ., ., ., ., ., ., ., ., ., ., ., ., .} 2 {., ., ., ., ., ., ., ., ., ., ., ., ., ., ., ., .} 3 {., x, x, x, x, x, ., ., x, ., ., ., ., ., x, x, .} 4 {., x, ., ., x, ., ., ., x, ., ., ., x, x, ., x, x} 5 {., x, x, x, x, ., ., ., x, ., x, x, ., x, ., x, .} 6 {., ., ., ., x, ., ., ., ., ., ., x, ., x, x, x, .} 7 {x, x, ., ., x, ., ., ., ., ., ., x, x, x, ., x, .} 8 {., x, ., ., ., ., ., ., ., ., ., ., ., ., ., ., .} 9 {x, x, ., ., ., ., ., ., ., ., ., ., ., ., ., ., .} Please implement a count_lakes function to count the number of lakes surrounded by lands connected by the input coordinates. .. code-block:: none Examples: count_lakes(image,(3,i)) -> 0 count_lakes(image,(3,f)) -> 1 count_lakes(image,(6,n)) -> 2 count_lakes(image,(7,b)) -> 0 count_lakes(image,(7,j)) -> 0 ---- There are two steps to solve this problem. First, we need to find the smallest sub-matrix which contains the input coordinates. Then we count the lake number by finding cluster of water. We can use DFS or BFS. The sample code uses DFS. .. literalinclude:: code/count_lakes_test.cpp :linenos: :lines: 5-43 :language: c++ :emphasize-lines: 10,20,6,16 Note when finding cluster of islands, we use 8 directions, but when finding cluster of water, we use 4 directions. This is because water is connected by up, down, left and right directions, but lands can be connected in a diagonal way. Another trick is mark the cell as a new value when traversing it in order to avoid using a visited set. .. only:: html - https://leetcode.com/discuss/interview-question/763001/count-number-of-freshwater-lakes-in-2d-matrix - https://leetcode.com/problems/number-of-closed-islands/