332. Reconstruct Itinerary

, , 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
    private static class Destination implements Comparable<Destination> {
        private final String to;
        private final int index;

        public Destination(String to, int index) {
            this.to = to;
            this.index = index;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Destination that = (Destination) o;
            return index == that.index && to.equals(that.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(to, index);
        }

        @Override
        public int compareTo(Destination o) {
            int value = this.to.compareTo(o.to);
            if (value == 0) {
                // 此处处理多张机票的场景，避免在 Set 中被去重
                return this.index - o.index;
            } else {
                return value;
            }
        }
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, TreeSet<Destination>> fromToDestinationMap = new HashMap<>();
        for (int i = 0; i < tickets.size(); i++) {
            List<String> ticket = tickets.get(i);
            fromToDestinationMap.computeIfAbsent(ticket.get(0), k -> new TreeSet<>())
                    .add(new Destination(ticket.get(1), i));
        }

        List<String> resultEndpoints = new ArrayList<>();
        Deque<String> endpoints = new LinkedList<>(); // 注意此处存储的是端点的个数
        boolean[] used = new boolean[tickets.size()]; // 注意此处存储的为边的个数
        endpoints.add("JFK");
        dfs(resultEndpoints, endpoints, fromToDestinationMap, used, "JFK");
        return resultEndpoints;
    }

    private void dfs(List<String> resultEndpoints, Deque<String> endpoints, Map<String, TreeSet<Destination>> fromToDestinationMap, boolean[] used, String from) {
        if (!resultEndpoints.isEmpty()) { // 注意此处避免多次收集，因为存在多条路径可达，只需收集最初到达的路径
            return;
        }

        if (endpoints.size() == used.length + 1) { // 注意端点的个数等于边的个数加 1
            resultEndpoints.addAll(endpoints);
            return;
        }

        TreeSet<Destination> destinationSet = fromToDestinationMap.get(from);
        if (destinationSet != null) {
            for (Destination destination : destinationSet) {
                // 注意不要忘记过滤已经使用过的机票
                if (used[destination.index]) {
                    continue;
                }

                endpoints.add(destination.to);
                used[destination.index] = true;
                dfs(resultEndpoints, endpoints, fromToDestinationMap, used, destination.to);
                endpoints.removeLast();
                used[destination.index] = false;
            }
        }
    }
}

注意题目没有说明存在多张相同的机票，但是需要处理该情况。Destination 类虽然没有用到 hashCode() 和 equals() 方法，但是根据规范，还是建议实现这两个方法，TreeSet 比较时仅使用了 compareTo() 方法，此时需要注意对索引的处理，避免相同机票在 Set 中被去重。

Hierholzer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        LinkedList<String> resultList = new LinkedList<>();
        Map<String, PriorityQueue<String>> fromToMap = new HashMap<>();
        for (List<String> ticket : tickets) {
            fromToMap.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>())
                    .offer(ticket.get(1));
        }

        dfs(resultList, fromToMap, "JFK");

        return resultList;
    }

    private void dfs(LinkedList<String> resultList, Map<String, PriorityQueue<String>> fromToMap, String from) {
        PriorityQueue<String> destinations = fromToMap.get(from);
        // 注意此处是 while
        while (destinations != null && !destinations.isEmpty()) {
            String destination = destinations.poll();
            dfs(resultList, fromToMap, destination);
        }
        resultList.addFirst(from);
    }
}

References

332. Reconstruct Itinerary
Comparable (Java Platform SE 8 )
TreeSet (Java Platform SE 8 )