332. Reconstruct Itinerary

332. 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:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

-------------------------
Solution #1
很直接的graph traversal，要对edge做visited，而不是node

class Solution {
    
    public List<String> findItinerary(String[][] tickets) {
        Map<String, Node> graph = buildGraph(tickets);
        
        List<String> rt = new ArrayList<>();
        rt.add("JFK");
        dfs(graph.get("JFK"), rt, tickets.length);
        
        return rt;
    }
    
    private boolean dfs(Node node, List<String> rt, int count) {
        if (count == 0) {
            return true;
        }
                
        for (int i = 0; i < node.next.size(); i++) {
            Node n = node.next.get(i);
            rt.add(n.airport);
            
            if (!node.visited[i]) {
                node.visited[i] = true;
                if (dfs(n, rt, count - 1)) return true;
                node.visited[i] = false;
            } 
            
            rt.remove(rt.size() - 1);
        }
        
        return false;
    }
    
    private Map<String, Node> buildGraph(String[][] tickets) {
        Map<String, Node> graph = new HashMap<>();
        
        for (String[] t : tickets) {
            if (!graph.containsKey(t[0])) {
                graph.put(t[0], new Node(t[0]));
            }
            if (!graph.containsKey(t[1])) {
                graph.put(t[1], new Node(t[1]));
            }
            
            graph.get(t[0]).next.add(graph.get(t[1]));
        }
        
        for (Node n : graph.values()) {
            Collections.sort(n.next, (a,b) -> a.airport.compareTo(b.airport));
            n.visited = new boolean[n.next.size()];
        }
        
        return graph;
    }
    
    class Node{
        public String airport;
        public List<Node> next;
        public boolean[] visited;
        public Node(String airport) {
            this.airport = airport;
            next = new ArrayList<>();
        }
    }
}

Solution #2 Eulerian Path Algorithm，题目已经说了路径一定存在
Eulerian Path的特点是一笔画，所有graph里面最多只有1个node有incoming degree - outgoing == 1, 只有一个node outgoing degree - incoming == 1. 所有要么是若干个环状，要么是一个单条路径 ＋ 若干个环状路径。算法就是遇到死路就back tracking继续。（看下面youtube的视频）

ref: https://www.youtube.com/watch?v=8MpoO2zA2l4
Code ref: https://leetcode.com/problems/reconstruct-itinerary/discuss/78768/Short-Ruby-Python-Java-C++

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();        
        
        for (String[] t : tickets) {
            if (!map.containsKey(t[0])) {
                map.put(t[0],new PriorityQueue<String>((a,b) -> a.compareTo(b)));
            }
            
            map.get(t[0]).add(t[1]);
        }
        
        List<String> rt = new ArrayList<>();
        dfs(map,rt,"JFK");
        
        Collections.reverse(rt);
        return rt;
    }
    
    private void dfs(Map<String, PriorityQueue<String>> map, List<String> rt, String ap) {
        
        while (map.containsKey(ap) && !map.get(ap).isEmpty()) {
            dfs(map,rt, map.get(ap).poll());
        }
        
        rt.add(ap);
    }
}

753. Cracking the Safe

753. Cracking the Safe

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.

Example 2:

Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.

Note:

1. n will be in the range [1, 4].
2. k will be in the range [1, 10].
3. k^n will be at most 4096.

----------------
题意是找一个最短的string，这个string得包含所有n长度的排列组合。最优的解是2个排列组合之间只相差一位，如 1234 -> 2345, *234 -> 234*. 解法是把234看作一个结点，12345为这个结点的边，把所有边都遍历一次就可以了
Eulerian path的定义https://en.wikipedia.org/wiki/Eulerian_path
用Hierholzer's algorithm来求path

O(k * k^n) time, Hierholzer's algorithm本来 是O(k^n), 但是以下实现方式每次都对k个边做检查来寻找未走过的边，所以有额外的k消耗
ToDo

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append("0");
        }
        
        Set<String> visited = new HashSet<>();
        visited.add(sb.toString());
        dfs(sb, visited, k, n);
        return sb.toString();
    }
    
    private void dfs(StringBuilder sb, Set<String> visited, int k, int n) {
        String node = sb.substring(sb.length() - n + 1);
        for (int i = k - 1; i >= 0; i--) {
            String s = node + Integer.toString(i);
            if (!visited.contains(s)) {
                visited.add(s);
                sb.append(Integer.toString(i));
                dfs(sb, visited, k, n);
            }
        }
    }
}

815. Bus Routes

815. Bus Routes

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 500.
• 0 <= routes[i][j] < 10 ^ 6.

------------------------
Solution #1 以bus route为⼀个node, 构建graph O(n * n * l) time, n为route的数量量，l为route的平均长度

class Solution {
    public int numBusesToDestination(int[][] routes, int s, int t) {
        if (s == t) return 0;
        
        Map<Integer, Cluster> graph = new HashMap<>();
        Queue<Integer> source = mergeRoutes(graph, routes, s);
        Set<Integer> visited = new HashSet<>();
        int len = 1;
        
        while (!source.isEmpty()) {
            
            int size = source.size();
            while (size > 0) {
                int top = source.poll();
                
                size--;
                if (visited.contains(top)) continue;
                visited.add(top);
                Cluster topC = graph.get(top);
                
                if (topC.elems.contains(t)) return len;
                for (int c : topC.neighbours) {
                    source.add(c);
                }
            }
            len++;
        }
        
        return -1;
    }
    
    private Queue<Integer> mergeRoutes(Map<Integer, Cluster> graph, int[][] routes, int s) {
        
        Queue<Integer> source = new LinkedList<>();
        
        for (int i = 0; i < routes.length; i++) {
            Cluster c = new Cluster(i, routes[i]);
            graph.put(i, c);
            
            for (int elem : routes[i]) {
                if (elem == s) source.add(i);
                    
                for (Map.Entry<Integer, Cluster> entry : graph.entrySet()) {
                    if (entry.getValue().elems.contains(elem)) {
                        entry.getValue().neighbours.add(i);
                        c.neighbours.add(entry.getValue().index);
                    }
                }
            }
        }

        return source;
    }
    
    class Cluster{
        public int index;
        public Set<Integer> elems;
        public Set<Integer> neighbours;
        
        public Cluster(int index, int[] route) {
            this.index = index;
            elems = new HashSet<>();
            for (int i : route) {
                elems.add(i);
            }
            
            neighbours = new HashSet<>();
        }
    }
}

Solution#2, 可以用stop当作node构建graph，与上面是相同复杂度
ref: https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS?page=1
Node是stop，neighbour是bus routes，visited里面存的也是bus route

class Solution {
    public int numBusesToDestination(int[][] routes, int s, int t) {
        if (s == t) return 0;
        
        Map<Integer, List<Integer>> stopToBus = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                int stop = routes[i][j];
                List<Integer> ro = stopToBus.getOrDefault(stop, new ArrayList<Integer>());
                ro.add(i);
                stopToBus.put(stop, ro);
            }
        }
        
        int r = 0;
        Queue<Integer> que = new LinkedList<>();
        que.add(s);
        
        while (!que.isEmpty()) {
            int len = que.size();
            r++;
            for (int i = 0; i < len; i++) {
                int cur = que.poll();    
                for (int bus : stopToBus.get(cur)) {
                    if (visited.contains(bus)) continue;
                    visited.add(bus);
                    for (int stop : routes[bus]) {
                        if (stop == t) return r;
                        que.add(stop);
                    }
                }
            }
        }
        
        return -1;
    }
}

399. Evaluate Division

399. 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.

----------------------

Solution #1, Graph dfs
O(n * m), n是graph大小，m是query的数量，应该可以用union-find来优化

class Solution {
    class Node {
        public String key;
        public Map<Node, Double> neighbors;
        public Node(String key) {
            this.key = key;
            neighbors = new HashMap<>();
        }
    }
    
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Node> graph = buildGraph(equations, values);
        
        int n = queries.length;
        double[] rt = new double[n];
        
        for (int i = 0; i < queries.length; i++) {
            rt[i] = dfs(graph, queries[i][0], queries[i][1], 1.0, new HashSet<String>());
        }
        
        return rt;
    }
    
    private double dfs(Map<String, Node> graph, String start, String end, double value, Set<String> visited) {
        if (!graph.containsKey(start) || !graph.containsKey(end) || visited.contains(start)) return -1.0;
        if (start.equals(end)) return value;
        
        visited.add(start);
        for (Map.Entry<Node, Double> entry : graph.get(start).neighbors.entrySet()) {
            double rt = dfs(graph, entry.getKey().key, end, value * entry.getValue(), visited);
            if (rt != -1.0) return rt;    
            
        }
        
        return -1.0;
    }
    
    private Map<String, Node> buildGraph(String[][] equations, double[] values) {
        Map<String, Node> graph = new HashMap<>();
        
        for (int i = 0; i < equations.length; i++) {
            String[] pair = equations[i];
            if (!graph.containsKey(pair[0])) {
                Node node = new Node(pair[0]);
                graph.put(pair[0], node);
            }
            
            if (!graph.containsKey(pair[1])) {
                Node node = new Node(pair[1]);
                graph.put(pair[1], node);
            }
            
            graph.get(pair[0]).neighbors.put(graph.get(pair[1]), values[i]);
            graph.get(pair[1]).neighbors.put(graph.get(pair[0]), 1 / values[i]);
        }
        
        return graph;
    }
}

Solution #2, Union Find，用被除数当作parent
ToDo: 加入UF本身的优化：size based

class Solution {
    
    class Node {
        public String key;
        public double val;
        public Node(String key) {
            this.key = key;
            val = 1;
        }
        
        public Node(String key, double val) {
            this.key = key;
            this.val = val;
        }
    }
    
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        
        Map<String, Node> map = new HashMap<>();
        Map<String, String> uf = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String[] pair = equations[i];
            if (!map.containsKey(pair[0])) {
                map.put(pair[0], new Node(pair[0]));
                uf.put(pair[0], pair[0]);
            }

            if (!map.containsKey(pair[1])) {
                map.put(pair[1], new Node(pair[1]));
                uf.put(pair[1], pair[1]);
            }

            Node parentOf1 = find(uf, map, pair[0]);
            Node parentOf2 = find(uf, map, pair[1]);

            if (!parentOf1.key.equals(parentOf2.key)) {
                uf.put(parentOf2.key, parentOf1.key);
                map.get(parentOf2.key).val = values[i] * parentOf1.val / parentOf2.val;
            }
        }

        double[] rt = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (!map.containsKey(queries[i][0]) || !map.containsKey(queries[i][1])) {
                rt[i] = -1.0;
                continue;
            }

            Node p1 = find(uf, map, queries[i][0]);
            Node p2 = find(uf, map, queries[i][1]);
            if (p1.key.equals(p2.key)) {
                rt[i] = p2.val / p1.val;
            }else {
                rt[i] = -1.0;
            }
        }

        return rt;
    }
        
    private Node find(Map<String, String> uf, Map<String, Node> map, String key) {
        String ori = key;
        double val = map.get(ori).val;

        while (!uf.get(key).equals(key)) {
            val *= map.get(uf.get(key)).val;
            key = uf.get(key);
        }

        uf.put(ori, key);
        map.get(ori).val = val;
        return new Node(key, val); // Use Node as Pair: return the key of parent, but the value of the original passed in key
    }
}

785. Is Graph Bipartite?

785. Is Graph Bipartite?

Given an undirected 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.

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 subsets.

Note:

• graph will have length in range [1, 100].
• graph[i] will contain integers in range [0, graph.length - 1].
• graph[i] will not contain i or duplicate values.
• The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

--------------------------
垂直一条线把graph分为2半，每一半的node只能有链接通向对面一半，不能跟相同一半的node有链接。

把2半分别标记别true跟false

Solution #1 DFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            if (!map.containsKey(i) && !dfs(map, graph, i, true)) return false;
        }
        
        return true;
    }
    
    private boolean dfs(Map<Integer, Boolean> map, int[][] graph, int node, boolean flag) {
        if (map.containsKey(node) && map.get(node) == flag) return false;
        if (map.containsKey(node)) return true;
        
        map.put(node, !flag);
        for (int neighbor : graph[node]) {
            if (!dfs(map, graph, neighbor, !flag)) return false;
        }
        
        return true;
    }
}

Solution #2 BFS

class Solution {
    
    public boolean isBipartite(int[][] graph) {
        Map map = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            if (!map.containsKey(i) && !bfs(map, graph, i)) return false;
        }
        
        return true;
    }
    
    private boolean bfs(Map map, int[][] graph, int node) {
        
        Queue que = new LinkedList<>();
        
        que.add(node);
        map.put(node, true);
        
        while (!que.isEmpty()) {
            int top = que.poll();
            for (int neighbor : graph[top]) {
                if (!map.containsKey(neighbor)) {
                    que.add(neighbor);
                    map.put(neighbor, !map.get(top));
                }else if (map.containsKey(neighbor) && map.get(neighbor) == map.get(top)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
}