【Leetcode Python题解】「2097. Valid Arrangement of Pairs」

在这篇技术博客中，我们将深入解析 LeetCode 的第 2097 题 —— Valid Arrangement of Pairs，并全面介绍如何从题意理解、图论建模到算法实现逐步解决问题。
题目：2097. Valid Arrangement of Pairs

问题描述

给定一个二维数组 pairs，其中 pairs[i] = [start, end]，我们需要重新排列这些数字对，使得相邻的两个数字对 [start1, end1] 和 [start2, end2] 满足以下条件：

  • end1 == start2。

输入数据保证一定存在这样一种合法的排列方式。

示例

示例 1

输入：

1
pairs = [[5,1],[4,5],[11,9],[9,4]]

输出：

1
[[11,9],[9,4],[4,5],[5,1]]

解释：
排列后满足条件：

  • end0 = 9 == 9 = start1
  • end1 = 4 == 4 = start2
  • end2 = 5 == 5 = start3

示例 2

输入：

1
pairs = [[1,3],[3,2],[2,1]]

输出：

1
[[1,3],[3,2],[2,1]]

问题建模：欧拉路径问题

这道题的本质是一个图论中的欧拉路径问题。我们将每个 pair [start, end] 看作一条从 start 到 end 的有向边，并试图找到一条路径能遍历所有边且满足条件。

什么是欧拉路径？

  • 定义：欧拉路径是一条路径，它能遍历图中每条边恰好一次。
  • 条件：
    1. 如果图中有且仅有两个节点的入度和出度不相等，则可以存在欧拉路径。
      • 起点：出度比入度大 1 的节点。
      • 终点：入度比出度大 1 的节点。
    2. 如果所有节点的入度等于出度，则图中存在欧拉回路。

解题思路

1. 图的构建

将每个 pair [start, end] 建模为有向边：

  • 节点为 start 和 end。
  • 边为从 start 到 end。

同时统计每个节点的 入度 和 出度，用于后续判断起点。

2. 寻找起点

通过入度和出度的统计：

  • 出度 - 入度 = 1 的节点是路径的起点。
  • 如果没有这样的节点，说明图中存在欧拉回路，可从任意节点开始。

3. Hierholzer 算法找路径

Hierholzer 算法 用于寻找欧拉路径，其核心步骤：

  1. 从起点开始，任意选择一条未访问的边走。
  2. 一直走直到走到死胡同（当前节点没有出边）。
  3. 回溯过程中记录路径。
  4. 最终记录的路径需要反转才能得到正确的顺序。

算法实现

下面是 Python 实现的完整代码：

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
from collections import defaultdict

def validArrangement(pairs):
    # 构建图
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    out_degree = defaultdict(int)
    
    for start, end in pairs:
        graph[start].append(end)
        out_degree[start] += 1
        in_degree[end] += 1
    
    # 寻找起点
    start_node = pairs[0][0]  # 默认起点
    for node in graph:
        if out_degree[node] - in_degree[node] == 1:
            start_node = node
            break
    
    # Hierholzer算法
    path = []
    def dfs(current_node):
        while graph[current_node]:
            next_node = graph[current_node].pop()
            dfs(next_node)
            path.append([current_node, next_node])
    
    dfs(start_node)
    return path[::-1]

代码解析

图的构建

使用 defaultdict 来存储图的邻接表，以及统计每个节点的入度和出度：

1
2
3
4
5
6
7
8
graph = defaultdict(list)
in_degree = defaultdict(int)
out_degree = defaultdict(int)

for start, end in pairs:
    graph[start].append(end)
    out_degree[start] += 1
    in_degree[end] += 1

寻找起点

根据入度和出度的统计规则：

1
2
3
4
5
start_node = pairs[0][0]  # 默认值
for node in graph:
    if out_degree[node] - in_degree[node] == 1:
        start_node = node
        break

Hierholzer算法

通过深度优先搜索（DFS）找到路径：

1
2
3
4
5
6
path = []  # 存储路径
def dfs(current_node):
    while graph[current_node]:  # 当前节点还有出边
        next_node = graph[current_node].pop()  # 获取并删除边
        dfs(next_node)
        path.append([current_node, next_node])  # 记录路径

示例运行

以 pairs = [[5,1],[4,5],[11,9],[9,4]] 为例：

图的状态

1
2
3
4
11 → 9
 9 → 4
 4 → 5
 5 → 1

执行过程

  1. 从节点 11 开始，DFS 遍历：

    • 走 11 → 9，移除边。
    • 走 9 → 4，移除边。
    • 走 4 → 5，移除边。
    • 走 5 → 1，移除边。

  2. 回溯记录路径：

    • path = [[5,1], [4,5], [9,4], [11,9]]

  3. 反转路径得到最终结果：

    1
    [[11,9], [9,4], [4,5], [5,1]]

算法复杂度

  • 时间复杂度：O(E)，其中 E 是边的数量。
    • 构建图需要 O(E)。
    • DFS 遍历每条边需要 O(E)。
  • 空间复杂度：O(E)，用于存储图的邻接表和结果路径。

Python 技巧补充

最后，我们补充一些代码中用到的一些 Python 技巧。

1. 闭包（Closure）

闭包 是指在一个函数内部定义另一个函数时，内部函数可以访问外部函数的变量，即使外部函数已经执行完毕。

在代码中，闭包的作用是通过内部函数访问和修改外部作用域的变量，而无需通过函数参数显式传递。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def outer():
    x = 10  # 外部变量

    def inner():
        nonlocal x  # 指定使用外部变量
        x += 1
        print(x)

    return inner

closure_func = outer()  # 返回 inner 函数
closure_func()  # 输出 11
closure_func()  # 输出 12

在本文的算法中，dfs() 函数利用闭包访问 path 列表，避免了通过参数显式传递路径的复杂操作。

为什么不需要将 path 作为参数？

  • 易读性：闭包让代码更加直观，避免传递多个参数。
  • 效率：闭包直接操作外部变量，避免在递归过程中传递和合并路径。

2. defaultdict 与 Counter

Python 的 collections 模块提供了许多工具类，其中 defaultdict 和 Counter 是本题的核心工具。

defaultdict

defaultdict 是字典的一个子类，可以为不存在的键提供默认值，从而避免访问不存在键时抛出 KeyError。

使用方式：
1
2
3
4
5
6
7
8
9
from collections import defaultdict

# 默认值是列表
graph = defaultdict(list)
graph[1].append(2)
graph[2].append(3)

print(graph)  # 输出：{1: [2], 2: [3]}
print(graph[3])  # 输出：[]，不会报错

在本文中，defaultdict 被用作图的邻接表，简化了图的构建和更新操作。

Counter

Counter 是字典的子类，用于统计元素的出现次数。它将每个元素作为键，出现次数作为值。

使用方式：
1
2
3
4
from collections import Counter

counts = Counter([1, 2, 2, 3, 3, 3])
print(counts)  # 输出：Counter({3: 3, 2: 2, 1: 1})

在本文中，可以通过 Counter 快速统计每个节点的入度和出度。

总结

这道题通过将数字对建模为图的欧拉路径问题，使用 Hierholzer 算法高效地找到合法排列。这种图论问题的建模方法不仅提升了题目理解，还为类似问题提供了通用解法。

希望这篇博客能帮助你彻底掌握这道题！如果你有其他问题，欢迎交流！