配對的有效排列

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中文網其他相關文章！