題目

https://leetcode.com/problems/reconstruct-itinerary/

題解

要把 next 數組按照字典序排列，所以用了 sorted 集合。兩個坑：

• 必須從 JFK 開始
• 同一個路線會重復出現

最樸素的思路 DFS，還好沒超時。分析過程見下圖~

后來根據測試用例發現路線會重復。。

import java.util.*; import java.util.concurrent.ConcurrentSkipListMap;class Vertex {String val;SortedMap<String, Integer> next;public Vertex(String val) {this.val = val;this.next = new ConcurrentSkipListMap<>();}public void incr(String next) {Integer count = this.next.get(next);if (count == null) this.next.put(next, 1);else this.next.put(next, count + 1);}public void decr(String next) {int count = this.next.get(next) - 1;if (count == 0) this.next.remove(next);else this.next.put(next, count);} }class Solution {int size;public List<String> findItinerary(List<List<String>> tickets) {size = tickets.size();Map<String, Vertex> graph = new HashMap<>();for (List<String> ticket : tickets) {graph.putIfAbsent(ticket.get(0), new Vertex(ticket.get(0)));graph.putIfAbsent(ticket.get(1), new Vertex(ticket.get(1)));graph.get(ticket.get(0)).incr(ticket.get(1));}// dfs 并關注出度Stack<String> stack = new Stack<>();tryDFS(graph, "JFK", stack);System.out.println(stack);return stack;}public boolean tryDFS(Map<String, Vertex> graph, String from, Stack<String> stack) {stack.push(from);System.out.println(graph.get(from).next);if (graph.get(from).next.isEmpty()) {if (stack.size() == size + 1) {return true;} else {stack.pop();return false;}}for (String next : graph.get(from).next.keySet()) { // 只要有一條可行路徑 就返回graph.get(from).decr(next);if (tryDFS(graph, next, stack)) return true; // 此路可行else graph.get(from).incr(next); // 此路不可行}// 沒有遇到可行路徑stack.pop();return false;} }

總結

以上是生活随笔為你收集整理的leetcode 332. Reconstruct Itinerary | 332. 重新安排行程（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。