2097。有效的配對排列

難度：難

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

給定一個(gè)0索引 2D整數(shù)數(shù)組對，其中pairs[i] = [start_i, end_i]。如果對于每個(gè)索引 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]]
• 解釋：_{這是一個(gè)有效的排列，因?yàn)?end}i-1 _{始終等于 start}i
  。
  • _結(jié)束0 _{= 9 == 9 = 開始}1
  • _結(jié)束1 _{= 4 == 4 = 開始}2
  • _結(jié)束2 _{= 5 == 5 = 開始}3

示例2：

• 輸入：
對 = [[1,3],[3,2],[2,1]]
• 輸出：
[[1,3],[3,2],[2,1]]
• 解釋：_{這是一個(gè)有效的排列，因?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]] 也是有效的。

示例 3：

• 輸入：
對 = [[1,2],[1,3],[2,1]]
• 輸出：
[[1,2],[2,1],[1,3]]
• 解釋：_{這是一個(gè)有效的排列，因?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)換成圖形問題嗎？
將這些對視為邊，將每個(gè)數(shù)字視為一個(gè)節(jié)點(diǎn)。
我們必須找到該圖的歐拉路徑。可以使用Hierholzer算法。

解決方案：

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

關(guān)鍵步驟：

1. 圖表示：對中的每個(gè)唯一數(shù)字將是一個(gè)節(jié)點(diǎn)，每對將是從 start[i] 到 end[i] 的一條邊。
2. 歐拉路徑準(zhǔn)則：
   • 如果恰好有兩個(gè)節(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ì)劃：

• 使用哈希圖構(gòu)建圖來存儲(chǔ)鄰接列表（每個(gè)節(jié)點(diǎn)及其連接的節(jié)點(diǎn)）。
• 跟蹤每個(gè)節(jié)點(diǎn)的度（入度和出度）。
• 使用 Hierholzer 算法求歐拉路徑。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：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)建:

   • 我們使用鄰接列表構(gòu)建圖，其中每個(gè)鍵都是起始節(jié)點(diǎn)，值是結(jié)束節(jié)點(diǎn)列表。
   • 我們還維護(hù)每個(gè)節(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 開始，重復(fù)跟蹤邊，通過從鄰接列表中刪除它們來將它們標(biāo)記為已訪問。
   • 一旦到達(dá)沒有更多傳出邊的節(jié)點(diǎn)，我們就會(huì)回溯并構(gòu)建結(jié)果。

4. 返回結(jié)果:

   • 由于我們回溯的方式，結(jié)果是以相反的順序構(gòu)造的，所以我們最后將其反轉(zhuǎ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]]
?>

時(shí)間復(fù)雜度：

• 構(gòu)建圖表：O(n)，其中 n 是對的數(shù)量。
• Hierholzer 算法：O(n)，因?yàn)槊織l邊都被訪問一次。
• 總體時(shí)間復(fù)雜度：O(n)。

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

聯(lián)系鏈接

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

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

• 領(lǐng)英
• GitHub

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