欧拉回路，Hierholzer算法

Reconstruct Itinerary

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

• 原题给的是 edges，所以图是自己用 hashmap 建的。

  • min heap 可以自动保证先访问 lexicographical order 较小的；

  • 同时 poll 出来的 node 自动删除，免去了用 List 的话要先 collections.sort 再 remove 的麻烦。

  • 这种以 “edge” 为重心的算法多靠 heap，比如 dijkstra.

一次AC, 想清楚了代码很简单

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
        for(String[] t: tickets){
            if(!map.containsKey(t[0])) map.put(t[0], new PriorityQueue<String>());
            map.get(t[0]).offer(t[1]);
        }

        Stack<String> stack = new Stack<String>();
        List<String> ans = new ArrayList<String>();
        stack.push("JFK");
        while(!stack.isEmpty()){
            PriorityQueue<String> pq = map.get(stack.peek());
            if(pq==null || pq.isEmpty()){
                ans.add(0, stack.pop());
            }
            else
                stack.push(pq.poll());
        }
        return ans;
    }
}

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);
    }
}

密码锁破解序列

首先你要弄明白你面对的是一个神马密码锁，它的特性是这样的： 一个长度为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 我觉得没啥问题。+

参考资料

http://poj.org/problem?id=1780

http://xwk.iteye.com/blog/2129621

https://en.wikipedia.org/wiki/Lyndon_word

https://en.wikipedia.org/wiki/De_Bruijn_graph

public class EulerSolution {
    int n, k, v;
    int[] edge;
    StringBuilder sequence;

    public String crackSequence(int k, int n) {
        this.n = n;
        this.k = k;
        v = 1; for (int i = 0; i < n - 1; ++i) v *= k; // vertices are n-1 bit radix k number.
        edge = new int[v]; // edge list
        sequence = new StringBuilder();
        dfs(0);
//        for (int i = 0; i < n - 1; ++i) sequence.append(0); 
        return sequence.reverse().toString();
    }

    // Hierholzer's algorithm
    private void dfs(int u) {
        while (edge[u] != k) {
            int i = edge[u]++;
            dfs((u * k + i) % v);
            sequence.append(i);
        }
    }

    public static void main(String[] args) {
        System.out.println(new EulerSolution().crackSequence(9, 4).length());
    }
}