LeetCode 332. 重新安排行程

Categories:

题目描述
思路分析
1. 解法一：Hierholzer 欧拉路径（推荐）
相似题目

题目描述

✅ 332. 重新安排行程

思路分析

解法一：Hierholzer 欧拉路径（推荐）

核心思路：

将机票视为有向边，目标是字典序最小的欧拉路径。

对每个起点的目的地按字典序放入最小堆。

使用 DFS 的后序加入路径，最终反转得到答案。

复杂度分析：

时间复杂度：O(E log E)，其中 E 表示机票数量。

空间复杂度：O(E)，用于图与递归栈。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> ticket : tickets) {
            graph.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>())
                    .offer(ticket.get(1));
        }

        List<String> path = new ArrayList<>();
        dfs("JFK", graph, path);
        Collections.reverse(path);
        return path;
    }

    private void dfs(String node, Map<String, PriorityQueue<String>> graph, List<String> path) {
        PriorityQueue<String> heap = graph.get(node);
        while (heap != null && !heap.isEmpty()) {
            dfs(heap.poll(), graph, path);
        }
        path.add(node);
    }
}

import "container/heap"

type StringHeap []string

func (h StringHeap) Len() int { return len(h) }
func (h StringHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h StringHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *StringHeap) Push(x interface{}) { *h = append(*h, x.(string)) }
func (h *StringHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func findItinerary(tickets [][]string) []string {
	graph := make(map[string]*StringHeap)
	for _, ticket := range tickets {
		from, to := ticket[0], ticket[1]
		if graph[from] == nil {
			h := &StringHeap{}
			heap.Init(h)
			graph[from] = h
		}
		heap.Push(graph[from], to)
	}

	path := make([]string, 0)
	var dfs func(node string)
	dfs = func(node string) {
		heapRef := graph[node]
		for heapRef != nil && heapRef.Len() > 0 {
			next := heap.Pop(heapRef).(string)
			dfs(next)
		}
		path = append(path, node)
	}

	dfs("JFK")

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

相似题目

题目	难度	考察点
2097. 合法重新排列数对	困难	欧拉路径
753. 破解保险箱	困难	欧拉路径
207. 课程表	中等	图拓扑
210. 课程表 II	中等	图拓扑
332. 重新安排行程	中等	欧拉路径

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/53257675