# 欧拉回路，Hierholzer算法

## [Reconstruct Itinerary](https://leetcode.com/problems/reconstruct-itinerary/)

dietpepsi 你这个贱人。。我搞了半天才发现这题不是简单的 DFS，而是欧拉回路。。。

### 因为我们一定可以从 JFK 出发并回到 JFK ，则 JFK 一定是图中的奇点，有奇数的 in+out degrees;

### Greedy DFS, building the route backwards when retreating.

这题其实和我之前用 DFS 处理 topological sort 的代码非常像，主要区别在于存 graph 的方式不同，这里是一个 String 直接连着对应的 next nodes，而且形式是 min heap:

> * **原题给的是 edges，所以图是自己用 hashmap 建的。**
>   * **min heap 可以自动保证先访问 lexicographical order 较小的；**
>   * **同时 poll 出来的 node 自动删除，免去了用 List 的话要先 collections.sort 再 remove 的麻烦。**
>   * **这种以 “edge” 为重心的算法多靠 heap，比如 dijkstra.**

```java
public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        LinkedList<String> list = new LinkedList<>();

        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for(String[] ticket : tickets){
            if(!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<String>());

            map.get(ticket[0]).add(ticket[1]);
        }

        dfs(list, "JFK", map);

        return new ArrayList<String>(list);
    }

    private void dfs(LinkedList<String> list, String airport, HashMap<String, PriorityQueue<String>> map){
        while(map.containsKey(airport) && !map.get(airport).isEmpty()){
            dfs(list, map.get(airport).poll(), map);
        }
        list.offerFirst(airport);
    }
}
```

## [密码锁破解序列 ](http://www.1point3acres.com/bbs/thread-166111-1-1.html)

首先你要弄明白你面对的是一个神马密码锁，它的特性是这样的： 一个长度为n=4的密码框，一个键盘有k=10个按键，分别是0\~9。 你输入0000，系统会验证0000是否是正确密码。 这时候你再输入一个1，不同的密码锁有不同的处理方式 一种会reset，也就是说前面的4个0消失了，你需要继续输入4个数供系统判断。 另一种不会reset，它会验证最近键入的4歌数字，即0001。 我们面对的是后一种。

如果是前一种的话，没啥好想的，破解序列就是4\*10000 但是后一种，可以做到长度为10003的破解序列覆盖所有可能的10000个4位数。 题目就是让你找到这个序列。

我觉得这道题在题意明确的情况下，把所有状态看成点，状态之间的转移看成边是比较自然的。 这样就有两种看法，一种就是把4位看成状态，一种就是把3位看成状态。 把4位看成状态的图上面找Hamilton回路，很显然是本题的答案，因为访问了每一个节点一次且只有一次。 把3位看成状态的图上面找欧拉回路可能需要给面试官解释一下。但我觉得还是比较好解释的。 因为每一条边其实代表了一种4位的状态，于是就很好解释了。 那么上面的DFS找欧拉回路的算法就是相当简单有效的解法了。在删除边和查找下一个没有访问的边的复杂度是O(1)的情况下这个算法的复杂度是O(E)的，也就是O(k^n)的，de Buijin构造算法不会比这个复杂度更好。 我这个实现没有用LinkedList或者Hash来保存边的信息，所以每次都是循环所有可能的边，也就是O(k)查找边，所以总的复杂度是O(k^(n+1))。 考虑到 k = 10 n = 4 我觉得没啥问题。

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Fd8d714367a265b8df5275ff411f3de95ef7a220a.png?generation=1614792532814978\&alt=media)