# LeetCode Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List<Node> neighbors;
}


Test case format:

For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).


Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.


Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.


Example 4:

Input: adjList = [[2],[1]]
Output: [[2],[1]]


Constraints:

• 1 <= Node.val <= 100
• Node.val is unique for each node.
• Number of Nodes will not exceed 100.
• There is no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

class Solution {
private:
unordered_map<int, UndirectedGraphNode*> graph;
public:
UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node)
{
if (node == NULL)
return NULL;
if (graph.find(node->label) != graph.end())
return graph[node->label];
UndirectedGraphNode* cur = new UndirectedGraphNode(node->label);
graph[cur->label] = cur;
for (auto& n : node->neighbors) {
cur->neighbors.push_back(cloneGraph(n));
}
return cur;
}
};

class Solution {
public:
Node* clone(Node* node, unordered_map<int, Node*> &hash) {
int val = node->val;
if (hash.find(val) != hash.end())return hash[val];
Node *cp = new Node(node->val);
hash[val] = cp;
for (int i = 0; i < node->neighbors.size(); ++i) {
int child = node->neighbors[i]->val;
if (hash.find(child) != hash.end()) {
cp->neighbors.push_back(hash[child]);
}
else {
cp->neighbors.push_back(clone(node->neighbors[i], hash));
}
}
return cp;
}

Node* cloneGraph(Node* node) {
if (node == NULL)return NULL;
unordered_map<int, Node*> hash;
return clone(node, hash);
}
};

# LeetCode Pacific Atlantic Water Flow

LeetCode Pacific Atlantic Water Flow Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean. Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~   ~   ~   ~   ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

# hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

### 输出

5 5
S.#.T
.....
.....
.....
.....

2

# LeetCode Minimum Height Trees

LeetCode Minimum Height Trees 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]]

        0
|
1
/ \
2   3

return [1] Example 2: Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
     0  1  2
\ | /
3
|
4
|
5

return [3, 4]
Note: (1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.” (2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
给定一个无向无环图，问以哪个顶点为根形成的有根树的树高是最小的，如果有多个这样的最小高度的有根树，则输出所有这样的根节点。 很有意思的一题，需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个，我想了想，应该最多只有两个吧。可以用反证法，假设有3个，则这3个根肯定会形成环，具体原因大家可以在纸上画个图举个例子就知道了。 然后我由题目的样例想到的是，把图转换为有根的最小高度的树，根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数，然后选两个度数最高的节点，对这两个点DFS求以他们为根时的树高，如果树高相同，说明这两个点都是答案，否则取树高更高的节点作为根节点。 但是很可惜，代码提交之后WA，错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。
8     3
\    \
2----0----5----6----7----9
/    /
4    1
在上图中，度数最多的前两个点是0和2，但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。 参考网上的题解，好巧妙呀。这种解法类似于剥洋葱，一层一层把叶子节点剥离掉，最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的，没剥掉一层，相当于树高减一，一直减，到最后还剩下的节点肯定就是根节点了。比如上图中，第一层剥掉8,3,9,4,1，变成下图
2----0----5----6----8
第二层剥掉之后变成下图
0----5----6
第三层剥掉之后就只剩下5号节点了，所以以5号节点为根，树的高度最低，只有3，而我的解法算出来的根节点0的树高是4，不是最小的。
5
剥洋葱的解法用BFS来实现就非常方便了，BFS天然就是一层循环就是剥掉一层。 代码中，初始时，我们把图转换为类似邻接表的结果，但是每个vector里存的是unordered_set，而不是list，因为剥洋葱的时候，比如第一层时剥掉8号节点时，我们同时需要把2号节点的邻接表中的8号节点删掉，所以用unordered_set.erase就非常方便。后面循环时，没剥一层，我们就检查一下，把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时，剩余的节点就是有根树的根节点。如果剩余两个节点，说明这两个节点的高度是一样的，都是正确答案。 代码如下： [cpp] class Solution { public: vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { if (n == 1)return{ 0 }; int m = edges.size(); vector<unordered_set<int>> graph(n, unordered_set<int>()); for (int i = 0; i < m; ++i) { graph[edges[i].first].insert(edges[i].second); graph[edges[i].second].insert(edges[i].first); } queue<int> q; for (int i = 0; i < n; ++i) { if (graph[i].size() == 1) q.push(i); } while (n > 2) { int t = q.size(); n -= t; while (t–) { int leaf = q.front(); q.pop(); for (auto par : graph[leaf]) { // only one par graph[par].erase(leaf); if (graph[par].size() == 1)q.push(par); } } } vector<int> ans; while (!q.empty()) { ans.push_back(q.front()); q.pop(); } return ans; } }; [/cpp] 本代码提交AC，用时79MS。]]>

# LeetCode Reconstruct Itinerary

LeetCode Reconstruct Itinerary 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:

1. 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"].
2. All airports are represented by three capital letters (IATA code).
3. 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.
给定一系列机票，每张机票标明了A→B的一段旅程，现在要求把所有的机票旅程连成一条完整的长距离航线，要求起点是JFK。如果有多条合法的航线，则输出字典序最小的那条。 显然要转换为图的问题，每个机场转换为一个点，每张机票转换为一条边，然后从JFK开始DFS，保留每条合法的航线，然后sort取字典序最小的航线。 把问题转换为图不难，使用hash给每个机场编号，然后新建一个图。在图中以JFK开始DFS也不难，每深入DFS一层，机票数目减1，当机票数目为0时，DFS结束，找到一条合法航线。 我一开始是这么做的，但是TLE了，因为这样可能会进行很多次DFS， 找到多条航线，还需要sort取字典序最小的航线。 有没有办法一次找到字典序最小的航线呢，只需要在DFS的时候，每次都从字典序最小的机场开始下一层DFS，这样第一次DFS成功的航线肯定是字典序最小的航线。 所以我们给机场编号的时候，先使用map记录，map会自动按key的字典序从小到大排好。然后遍历map重新编号，并且用hash2记录编号和机场的对应关系。这样，在DFS的时候，从0→n的遍历，就自动是按字典序从小到大遍历。 代码如下： [cpp] class Solution { private: bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) { if (lines == 0) return true; int n = hash2.size(); for (int i = 0; i < n; ++i) { // 字典序从小到大深搜 if (graph[start][i] > 0) { –graph[start][i]; ans += hash2[i]; if (dfs(ans, hash2, graph, i, lines – 1))return true; ++graph[start][i]; ans = ans.substr(0, ans.size() – 3); } } return false; } public: vector<string> findItinerary(vector<pair<string, string>> tickets) { map<string, int> hash1; vector<string> hash2; int cnt = 0, n = tickets.size(); for (int i = 0; i < tickets.size(); ++i) { // 记录 hash1[tickets[i].first] = 0; hash1[tickets[i].second] = 0; } for (auto it = hash1.begin(); it != hash1.end(); ++it) { it->second = cnt++; // 字典序从小到大编号 hash2.push_back(it->first); } vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图 for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]]; int start = hash1["JFK"]; string ans = "JFK"; dfs(ans, hash2, graph, start, n); // 深搜 vector<string> Itinerary; for (int i = 0; i <= ans.size() – 3; i += 3)Itinerary.push_back(ans.substr(i, 3)); return Itinerary; } }; [/cpp] 本代码提交AC，用时22MS。]]>

# LeetCode Evaluate Division

LeetCode Evaluate Division 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 input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
给定一系列的除法表达式，要计算另一些除法表达式的结果。比如知道a/b=2.0,b/c=3.0，问a/c=?。 本题的解法是把一系列表达式转换为图，比如a/b=2.0转换为a指向b的边，边的值为2.0，同时b指向a的边的值为1/2.0。如果要求a/c，则在图中找一条a到c的边，并且把走过的边的值乘起来。 构建图的过程先把表达式中的string编码成int，然后把已知的直连边加入到图中。对于要查询的边start/target，首先判断一下两个端点是否在图中，如果至少有一个端点不在图中，则无法求值，返回-1。否则，在图中DFS或BFS找到target，走过的路径乘积就是结果。 题目说明所有values都是正数，所以不存在除0问题。 DFS代码如下： [cpp] class Solution { private: bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) { graph[start][y] = graph[start][x] * graph[x][y]; graph[y][start] = 1.0 / graph[start][y]; if(y == target)return true; int n = graph.size(); for(int i = 0; i < n; ++i){ if(graph[start][i] == 0 && graph[y][i] != 0){ if(dfs(graph, start, y, i, target))return true; } } return false; } double helper(vector<vector<double>>& graph, int start, int target) { if (start == target)return 1.0; else if (graph[start][target] != 0.0)return graph[start][target]; int n = graph.size(); for (int y = 0; y < n; ++y) { if (y == start)continue; if (graph[start][y] != 0.0) { if (dfs(graph, start, start, y, target))return graph[start][target]; } } return -1.0; } public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { int cnt = 0, n = equations.size(); unordered_map<string, int> hash; for (int i = 0; i < n; ++i) { if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++; if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++; } vector<vector<double>> graph(cnt, vector<double>(cnt, 0)); for (int i = 0; i < n; ++i) { int x = hash[equations[i].first], y = hash[equations[i].second]; graph[x][x] = 1; graph[y][y] = 1; graph[x][y] = values[i]; graph[y][x] = 1.0 / values[i]; } vector<double> ans; for (int i = 0; i < queries.size(); ++i) { if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0); else { int x = hash[queries[i].first], y = hash[queries[i].second]; ans.push_back(helper(graph, x, y)); } } return ans; } }; [/cpp] 本代码提交AC，用时3MS。 BFS代码如下： [cpp] class Solution { private: double bfs(vector<vector<double>>& graph, int start, int target) { if (start == target)return 1.0; else if (graph[start][target] != 0.0)return graph[start][target]; int n = graph.size(); queue<int> q; for(int x = 0; x < n; ++x){ if(x != start && graph[start][x] != 0)q.push(x); } while(!q.empty()){ int x = q.front(); if(x == target) return graph[start][target]; q.pop(); for(int y = 0; y < n; ++y){ if(graph[start][y] == 0 && graph[x][y] != 0){ graph[start][y] = graph[start][x] * graph[x][y]; graph[y][start] = 1.0 / graph[start][y]; q.push(y); } } } return -1.0; } public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { int cnt = 0, n = equations.size(); unordered_map<string, int> hash; for (int i = 0; i < n; ++i) { if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++; if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++; } vector<vector<double>> graph(cnt, vector<double>(cnt, 0)); for (int i = 0; i < n; ++i) { int x = hash[equations[i].first], y = hash[equations[i].second]; graph[x][x] = 1; graph[y][y] = 1; graph[x][y] = values[i]; graph[y][x] = 1.0 / values[i]; } vector<double> ans; for (int i = 0; i < queries.size(); ++i) { if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0); else { int x = hash[queries[i].first], y = hash[queries[i].second]; ans.push_back(bfs(graph, x, y)); } } return ans; } }; [/cpp] 本代码提交AC，用时0MS，类似的题BFS显然要比DFS快，而且这题用BFS思路更清晰。]]>