配对的有效排列-php教程-PHP中文网

Valid Arrangement of Pairs

2097。有效的配对排列

难度：难

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

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

返回任何对的有效排列

。

注意

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

示例1：

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

示例2：

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

示例 3：

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

约束：

^{1 5}
_{0 i_，结束i⁹}
_开始i_!=结束i
存在

提示：

解决方案：

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

关键步骤：

图表示：对中的每个唯一数字将是一个节点，每对将是从 start[i] 到 end[i] 的一条边。
欧拉路径准则：
- 如果恰好有两个节点的度数为奇数，则欧拉路径存在，其余节点的度数必须为偶数。
- 我们需要确保图是连通的（尽管这是由问题陈述保证的）。
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 的节点开始（如果存在这样的节点）。
- 如果不存在这样的节点，则图是平衡的，我们可以从任何节点开始。
Hierholzer 算法:
- 我们从 startNode 开始，重复跟踪边，通过从邻接列表中删除它们来将它们标记为已访问。
- 一旦到达没有更多传出边的节点，我们就会回溯并构建结果。
返回结果:
- 由于我们回溯的方式，结果是以相反的顺序构造的，所以我们最后将其反转。

示例输出：

<?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]]
?>

登录后复制