配对的有效排列

2097。有效的配对排列

难度：难

主题：深度优先搜索、图、欧拉电路

给定一个0索引 2D整数数组对，其中pairs[i] = [start_i, end_i]。如果对于每个索引 i，其中 1 ，则对的排列是有效_{。 pairs.length，我们有 end}i-1 _{== start}i

.

返回任何对的有效排列

。

注意

：将生成输入，以便存在有效的配对排列。

示例1：

• 输入：
对 = [[5,1],[4,5],[11,9],[9,4]]
• 输出：
[[11,9],[9,4],[4,5],[5,1]]
• 解释：_{这是一个有效的排列，因为 end}i-1 _{始终等于 start}i
  。
  • _结束0 _{= 9 == 9 = 开始}1
  • _结束1 _{= 4 == 4 = 开始}2
  • _结束2 _{= 5 == 5 = 开始}3

示例2：

• 输入：
对 = [[1,3],[3,2],[2,1]]
• 输出：
[[1,3],[3,2],[2,1]]
• 解释：_{这是一个有效的排列，因为 end}i-1 _{始终等于 start}i
  。
  • _结束0 _{= 3 == 3 = 开始}1
  • _结束1 _{= 2 == 2 = 开始}2
  排列 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 也是有效的。

示例 3：

• 输入：
对 = [[1,2],[1,3],[2,1]]
• 输出：
[[1,2],[2,1],[1,3]]
• 解释：_{这是一个有效的排列，因为 end}i-1 _{始终等于 start}i
  。
  • _结束0 _{= 2 == 2 = 开始}1
  • _结束1 _{= 1 == 1 = 开始}2

约束：

• ^{1 5}
pairs[i].length == 2
• _{0 i，结束i ⁹}
• _开始i _!=结束i
没有两对是完全相同的。
• 存在
有效的配对排列。

提示：

你能把它转换成图形问题吗？
将这些对视为边，将每个数字视为一个节点。
我们必须找到该图的欧拉路径。可以使用Hierholzer算法。

解决方案：

我们可以将其视为图论中的欧拉路径问题。在这种情况下，这些对可以被视为边，并且这些对内的值（开始和结束）可以被视为节点。我们需要找到一条欧拉路径，该路径每一条边都只使用一次，并且一条边的终点必须与下一条边的起点相匹配。

关键步骤：

1. 图表示：对中的每个唯一数字将是一个节点，每对将是从 start[i] 到 end[i] 的一条边。
2. 欧拉路径准则：
   • 如果恰好有两个节点的度数为奇数，则欧拉路径存在，其余节点的度数必须为偶数。
   • 我们需要确保图是连通的（尽管这是由问题陈述保证的）。
3. Hierholzer's Algorithm：该算法可用于求欧拉路径。它涉及：
   • 从具有奇数度数的节点（如果有）开始。
   • 遍历边缘，将其标记为已访问。
   • 如果到达的节点有未使用的边，则继续遍历，直到所有边都被使用。

计划：

• 使用哈希图构建图来存储邻接列表（每个节点及其连接的节点）。
• 跟踪每个节点的度（入度和出度）。
• 使用 Hierholzer 算法求欧拉路径。

让我们用 PHP 实现这个解决方案：2097。有效的配对排列

<?php
/**
 * @param Integer[][] $pairs
 * @return Integer[][]
 */
function validArrangement($pairs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>

解释：

1. 图构建:

   • 我们使用邻接列表构建图，其中每个键都是起始节点，值是结束节点列表。
   • 我们还维护每个节点的出度和入度，这将帮助我们找到欧拉路径的起始节点。

2. 查找起始节点:

   • 欧拉路径从出度比入度大 1 的节点开始（如果存在这样的节点）。
   • 如果不存在这样的节点，则图是平衡的，我们可以从任何节点开始。

3. Hierholzer 算法:

   • 我们从 startNode 开始，重复跟踪边，通过从邻接列表中删除它们来将它们标记为已访问。
   • 一旦到达没有更多传出边的节点，我们就会回溯并构建结果。

4. 返回结果:

   • 由于我们回溯的方式，结果是以相反的顺序构造的，所以我们最后将其反转。

示例输出：

<?php
/**
 * @param Integer[][] $pairs
 * @return Integer[][]
 */
function validArrangement($pairs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>

时间复杂度：

• 构建图表：O(n)，其中 n 是对的数量。
• Hierholzer 算法：O(n)，因为每条边都被访问一次。
• 总体时间复杂度：O(n)。

这种方法通过将问题视为有向图中的欧拉路径问题，有效地找到对的有效排列。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是配对的有效排列的详细内容。更多信息请关注PHP中文网其他相关文章！