# 欧拉回路，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 我觉得没啥问题。

![](/files/-MUt7bnqnWkXXN3GjK4G)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/topological_sortff0c_tuo_pu_pai_xu/ou_la_hui_lu_ff0c_hierholzer_suan_fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.