Han Zhu's Study Notes

Equations are given in the format  A / B = k , where  A  and  B  are variables represented as strings, and  k  is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 . Example: Given  a / b = 2.0, b / c = 3.0. queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return  [6.0, 0.5, -1.0, 1.0, -1.0 ]. The input is:  vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> . According to the example above: equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. The...

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 . Note : 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 . Thought process: A tree is a graph that doesn't have a cycle. BFS. When a node is polled from queue, iterate through its neighbors. If any of them is visited but not the node's parent, there is a cycle. If there are no edges, then the graph is a tree only if it has only one node. Build graph. Use a map of int -> list of int. Iterate through the edg...

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. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. 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 the correct course order is  [0,1] 4, [[1,0],[2,0],[3,1],[3,2]] 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] . Note:...

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. click to show more hints. Hints: This problem is ...