332. 重新安排行程

题目描述

输入一组机票 tickets，每张机票 tickets[i] = [from, to] 表示一段从机场 from 飞往机场 to 的航程。机场用三个大写字母表示。

所有机票属于同一位旅客。他从 "JFK" 出发，要把每张机票都用掉，而且每张只能用一次。请按飞行顺序排出他经过的机场。

合法行程可能不止一种。此时把行程看成字符串列表，按字典序比较，返回最小的那一种。例如 ["JFK","LGA"] 比 ["JFK","LGB"] 小。

返回行程中依次经过的机场列表，第一个元素是 "JFK"。题目保证至少有一种合法行程。

示例 1

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

解释：机票只能连成一条路线：JFK -> MUC -> LHR -> SFO -> SJC。

示例 2

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]

解释：["JFK","SFO","ATL","JFK","ATL","SFO"] 也合法，但字典序更大。

数据范围

1 <= tickets.length <= 300
tickets[i].length == 2
from.length == 3
to.length == 3
from 和 to 只含大写英文字母
from != to

解题思路：Hierholzer（显式栈）

每张机票是一条有向边，要找一条用完所有边的欧拉路径，用 Hierholzer 算法。把每个机场的出边按字典序排好，每次走最小的那条。用栈模拟 DFS：栈顶还有出边就沿着走；没有出边了（走进死胡同），就把它弹出加入 route。最后 route 反过来就是行程。

为什么正确

一个机场只有在它的出边全部用完后才会被加入 route，所以 route 是行程的逆序：先入 route 的是最后到达的地方。

复杂度分析

时间 O(E log E)（排序），空间 O(E)。

易错点

贪心地按字典序直接走可能走进死胡同（如 JFK→KUL 无法返回）。Hierholzer 的“走不动才加入 route、最后反转”恰好把死胡同放到行程末尾。另外出边要按降序存放，才能用 pop() 每次取最小的。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)
        route = []
        stack = ['JFK']
        while stack:
            while graph[stack[-1]]:
                stack.append(graph[stack[-1]].pop())
            route.append(stack.pop())
        return route[::-1]

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> graph = new HashMap<>();
        List<List<String>> sorted = new ArrayList<>(tickets);
        sorted.sort((x, y) -> { int c = y.get(0).compareTo(x.get(0)); return c != 0 ? c : y.get(1).compareTo(x.get(1)); });
        for (List<String> t : sorted) {
            graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
        }
        LinkedList<String> route = new LinkedList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            List<String> out = graph.getOrDefault(stack.peek(), new ArrayList<>());
            while (!out.isEmpty()) {
                stack.push(out.remove(out.size() - 1));
                out = graph.getOrDefault(stack.peek(), new ArrayList<>());
            }
            route.addFirst(stack.pop());
        }
        return route;
    }
}

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>> graph;
        sort(tickets.rbegin(), tickets.rend());
        for (auto& t : tickets) {
            graph[t[0]].push_back(t[1]);
        }
        vector<string> route;
        vector<string> stk = {"JFK"};
        while (!stk.empty()) {
            while (!graph[stk.back()].empty()) {
                string nxt = graph[stk.back()].back();
                graph[stk.back()].pop_back();
                stk.push_back(nxt);
            }
            route.push_back(stk.back());
            stk.pop_back();
        }
        reverse(route.begin(), route.end());
        return route;
    }
};

func findItinerary(tickets [][]string) []string {
	graph := map[string][]string{}
	sort.Slice(tickets, func(i, j int) bool {
		if tickets[i][0] != tickets[j][0] {
			return tickets[i][0] > tickets[j][0]
		}
		return tickets[i][1] > tickets[j][1]
	})
	for _, t := range tickets {
		graph[t[0]] = append(graph[t[0]], t[1])
	}
	route := []string{}
	stack := []string{"JFK"}
	for len(stack) > 0 {
		for len(graph[stack[len(stack)-1]]) > 0 {
			top := stack[len(stack)-1]
			out := graph[top]
			graph[top] = out[:len(out)-1]
			stack = append(stack, out[len(out)-1])
		}
		route = append(route, stack[len(stack)-1])
		stack = stack[:len(stack)-1]
	}
	for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
		route[i], route[j] = route[j], route[i]
	}
	return route
}

var findItinerary = function(tickets) {
    const graph = new Map();
    const sorted = [...tickets].sort((x, y) => x[0] !== y[0] ? (x[0] < y[0] ? 1 : -1) : (x[1] < y[1] ? 1 : x[1] > y[1] ? -1 : 0));
    for (const [a, b] of sorted) {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a).push(b);
    }
    const route = [];
    const stack = ['JFK'];
    while (stack.length) {
        while ((graph.get(stack[stack.length - 1]) || []).length) {
            stack.push(graph.get(stack[stack.length - 1]).pop());
        }
        route.push(stack.pop());
    }
    return route.reverse();
};

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, string[]>();
    const sorted = [...tickets].sort((x, y) => x[0] !== y[0] ? (x[0] < y[0] ? 1 : -1) : (x[1] < y[1] ? 1 : x[1] > y[1] ? -1 : 0));
    for (const [a, b] of sorted) {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a)!.push(b);
    }
    const route: string[] = [];
    const stack = ['JFK'];
    while (stack.length) {
        while ((graph.get(stack[stack.length - 1]) || []).length) {
            stack.push(graph.get(stack[stack.length - 1])!.pop()!);
        }
        route.push(stack.pop()!);
    }
    return route.reverse();
}

载入编辑器，自己跑一遍 →

其他解法

两种写法都是 Hierholzer 求欧拉路径：递归版用系统调用栈，主解法用显式栈避免递归过深。

解法 2：Hierholzer（递归）时间 O(E log E)，空间 O(E)

把每个机场的目的地按字典序倒序存放，这样从末尾弹出的就是字典序最小的目的地。从 JFK 开始递归：只要当前机场还有未用的机票，就弹出一张并递归进入目的地。当前机场的机票用完后把它加入路线。最后反转路线。

是官方题解的写法，递归代码更短，“无路可走时才入栈”的性质更直观。机票很多时递归很深，显式栈版本更稳妥。

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)
        route = []

        def dfs(u):
            while graph[u]:
                dfs(graph[u].pop())
            route.append(u)

        dfs('JFK')
        return route[::-1]

class Solution {
    Map<String, List<String>> graph = new HashMap<>();
    List<String> route = new ArrayList<>();

    void dfs(String u) {
        List<String> out = graph.get(u);
        while (out != null && !out.isEmpty()) {
            dfs(out.remove(out.size() - 1));
        }
        route.add(u);
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        List<List<String>> sorted = new ArrayList<>(tickets);
        sorted.sort((x, y) -> { int c = y.get(0).compareTo(x.get(0)); return c != 0 ? c : y.get(1).compareTo(x.get(1)); });
        for (List<String> t : sorted) graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
        dfs("JFK");
        Collections.reverse(route);
        return route;
    }
}

class Solution {
public:
    unordered_map<string, vector<string>> graph;
    vector<string> route;
    void dfs(const string& u) {
        while (!graph[u].empty()) {
            string v = graph[u].back();
            graph[u].pop_back();
            dfs(v);
        }
        route.push_back(u);
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        sort(tickets.rbegin(), tickets.rend());
        for (auto& t : tickets) graph[t[0]].push_back(t[1]);
        dfs("JFK");
        reverse(route.begin(), route.end());
        return route;
    }
};

func findItinerary(tickets [][]string) []string {
	graph := map[string][]string{}
	sort.Slice(tickets, func(i, j int) bool {
		if tickets[i][0] != tickets[j][0] {
			return tickets[i][0] > tickets[j][0]
		}
		return tickets[i][1] > tickets[j][1]
	})
	for _, t := range tickets {
		graph[t[0]] = append(graph[t[0]], t[1])
	}
	route := []string{}
	var dfs func(u string)
	dfs = func(u string) {
		for len(graph[u]) > 0 {
			out := graph[u]
			v := out[len(out)-1]
			graph[u] = out[:len(out)-1]
			dfs(v)
		}
		route = append(route, u)
	}
	dfs("JFK")
	for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
		route[i], route[j] = route[j], route[i]
	}
	return route
}

var findItinerary = function(tickets) {
    const graph = new Map();
    const sorted = [...tickets].sort((x, y) => x[0] !== y[0] ? (x[0] < y[0] ? 1 : -1) : (x[1] < y[1] ? 1 : x[1] > y[1] ? -1 : 0));
    for (const [a, b] of sorted) {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a).push(b);
    }
    const route = [];
    const dfs = (u) => {
        const out = graph.get(u);
        while (out && out.length > 0) {
            dfs(out.pop());
        }
        route.push(u);
    };
    dfs('JFK');
    return route.reverse();
};

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, string[]>();
    const sorted = [...tickets].sort((x, y) => x[0] !== y[0] ? (x[0] < y[0] ? 1 : -1) : (x[1] < y[1] ? 1 : x[1] > y[1] ? -1 : 0));
    for (const [a, b] of sorted) {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a)!.push(b);
    }
    const route: string[] = [];
    const dfs = (u: string): void => {
        const out = graph.get(u);
        while (out && out.length > 0) {
            dfs(out.pop()!);
        }
        route.push(u);
    };
    dfs('JFK');
    return route.reverse();
}

图论专题的其他题目

查看图论全部题目 →