2097。有效的配對排列

難度：難

主題：深度優(yōu)先搜尋、圖、歐拉電路

給定一個0索引 2D整數(shù)數(shù)組對，其中pairs[i] = [start_i, end_i]。如果對於每個索引 i，其中 1 ，則對的排列是有效_{。 pairs.length，我們有 end}i-1 _{== start}i

.

回傳任何對的有效排列

。

注意

：將產(chǎn)生輸入，以便存在有效的配對排列。

範(fàn)例1：

• 輸入：
對 = [[5,1],[4,5],[11,9],[9,4]]
• 輸出：
[[11,9],[9,4],[4,5],[5,1]]
• 解釋：_{這是一個有效的排列，因?yàn)?end}i-1 _{總是等於 start}i
  。
  • _結(jié)束0 _{= 9 == 9 = 開始}1
  • _結(jié)束1 _{= 4 == 4 = 開始}2
  • _結(jié)束2 _{= 5 == 5 = 開始}3

範(fàn)例2：

• 輸入：
對 = [[1,3],[3,2],[2,1]]
• 輸出：
[[1,3],[3,2],[2,1]]
• 解釋：_{這是一個有效的排列，因?yàn)?end}i-1 _{總是等於 start}i
  。
  • _結(jié)束0 _{= 3 == 3 = 開始}1
  • _結(jié)束1 _{= 2 == 2 = 開始}2
  排列 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 也是有效的。

範(fàn)例 3：

• 輸入：
對 = [[1,2],[1,3],[2,1]]
• 輸出：
[[1,2],[2,1],[1,3]]
• 解釋：_{這是一個有效的排列，因?yàn)?end}i-1 _{總是等於 start}i
  。
  • _結(jié)束0 _{= 2 == 2 = 開始}1
  • _結(jié)束1 _{= 1 == 1 = 開始}2

約束：

• ^{1 5}
pairs[i].length == 2
• _{0 i，結(jié)束i ⁹}
• _開始i _{!=結(jié)束}i
沒有兩對是完全相同的。
• 存在
有效的配對排列。

提示：

你能把它轉(zhuǎn)換成圖形問題嗎？
將這些對視為邊，將每個數(shù)字視為一個節(jié)點(diǎn)。
我們必須找到該圖的歐拉路徑?？梢允褂肏ierholzer演算法。

解：

我們可以將其視為圖論中的歐拉路徑問題。在這種情況下，這些對可以被視為邊，而這些對內(nèi)的值（開始和結(jié)束）可以被視為節(jié)點(diǎn)。我們需要找到一條歐拉路徑，該路徑每一條邊都只使用一次，並且一條邊的終點(diǎn)必須與下一條邊的起點(diǎn)相符。

關(guān)鍵步驟：

1. 圖表示：對中的每個唯一數(shù)字將是一個節(jié)點(diǎn)，每對將是從 start[i] 到 end[i] 的一條邊。
2. 歐拉路徑準(zhǔn)則：
   • 如果剛好有兩個節(jié)點(diǎn)的度數(shù)為奇數(shù)，則歐拉路徑存在，其餘節(jié)點(diǎn)的度數(shù)必須為偶數(shù)。
   • 我們需要確保圖是連通的（儘管這是由問題陳述保證的）。
3. Hierholzer's Algorithm：此演算法可用於求歐拉路徑。它涉及：
   • 從具有奇數(shù)度數(shù)的節(jié)點(diǎn)（如果有）開始。
   • 遍歷邊緣，將其標(biāo)記為已訪問。
   • 如果到達(dá)的節(jié)點(diǎn)有未使用的邊，則繼續(xù)遍歷，直到所有邊都被使用。

計(jì)劃：

• 使用雜湊圖建立圖來儲存鄰接列表（每個節(jié)點(diǎn)及其連接的節(jié)點(diǎn)）。
• 追蹤每個節(jié)點(diǎn)的度數(shù)（入度和出度）。
• 使用 Hierholzer 演算法求歐拉路徑。

讓我們用 PHP 實(shí)作這個解：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. 圖建構(gòu):

   • 我們使用鄰接列表建立圖，其中每個鍵都是起始節(jié)點(diǎn)，值是結(jié)束節(jié)點(diǎn)列表。
   • 我們也維護(hù)每個節(jié)點(diǎn)的出度和入度，這將有助於我們找到歐拉路徑的起始節(jié)點(diǎn)。

2. 找起始節(jié)點(diǎn):

   • 歐拉路徑從出度比入度大 1 的節(jié)點(diǎn)開始（如果有這樣的節(jié)點(diǎn)）。
   • 如果不存在這樣的節(jié)點(diǎn)，則圖是平衡的，我們可以從任何節(jié)點(diǎn)開始。

3. Hierholzer 演算法:

   • 我們從 startNode 開始，重複追蹤邊，透過從鄰接清單中刪除它們來將它們標(biāo)記為已存取。
   • 一旦到達(dá)沒有更多傳出邊的節(jié)點(diǎn)，我們就會回溯並建構(gòu)結(jié)果。

4. 回傳結(jié)果:

   • 由於我們回溯的方式，結(jié)果是以相反的順序建構(gòu)的，所以我們最後將其反轉(zhuǎn)。

範(fàn)例輸出：

<?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 是對的數(shù)量。
• Hierholzer 演算法：O(n)，因?yàn)槊織l邊都被訪問一次。
• 整體時間複雜度：O(n)。

這種方法透過將問題視為有向圖中的歐拉路徑問題，有效地找到對的有效排列。

聯(lián)絡(luò)連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是配對的有效排列的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！