2097. Susunan Pasangan yang Sah

Kesukaran: Sukar

Topik: Carian Pertama Kedalaman, Graf, Litar Eulerian

Anda diberi pasangan tatasusunan integer 2D yang indeks 0 dengan pasangan[i] = [mula_i, tamat_i]. Susunan pasangan adalah sah jika bagi setiap indeks i dengan 1 <= i < berpasangan.panjang, kita ada akhir_i-1 == mula_i.

Pulangan sebarang susunan pasangan yang sah.

Nota: Input akan dijana sedemikian rupa sehingga wujud susunan pasangan yang sah.

Contoh 1:

• Input: pasangan = [[5,1],[4,5],[11,9],[9,4]]
• Output: [[11,9],[9,4],[4,5],[5,1]]
• Penjelasan: Ini adalah susunan yang sah sejak akhir_i-1 sentiasa sama dengan permulaan_i.
  • tamat₀ = 9 == 9 = mula₁
  • tamat₁ = 4 == 4 = mula₂
  • tamat₂ = 5 == 5 = mula₃

Contoh 2:

• Input: pasangan = [[1,3],[3,2],[2,1]]
• Output: [[1,3],[3,2],[2,1]]
• Penjelasan: Ini adalah susunan yang sah sejak akhir_i-1 sentiasa sama dengan permulaan_i.
  • tamat₀ = 3 == 3 = mula₁
  • tamat₁ = 2 == 2 = mula₂
  • Peraturan [[2,1],[1,3],[3,2]] dan [[3,2],[2,1],[1,3]] juga sah.

Contoh 3:

• Input: pasangan = [[1,2],[1,3],[2,1]]
• Output: [[1,2],[2,1],[1,3]]
• Penjelasan: Ini adalah susunan yang sah sejak akhir_i-1 sentiasa sama dengan permulaan_i.
  • tamat₀ = 2 == 2 = mula₁
  • tamat₁ = 1 == 1 = mula₂

Kekangan:

• 1 <= pairs.length <= 10⁵
• pasangan[i].panjang == 2
• 0 <= mula_i, tamat_i <= 10⁹
• mula_i != tamat_i
• Tiada dua pasangan yang betul-betul sama.
• Terdapat wujud susunan pasangan yang sah.

Petunjuk:

1. Bolehkah anda menukar ini kepada masalah graf?
2. Anggap pasangan sebagai tepi dan setiap nombor sebagai nod.
3. Kita perlu mencari laluan Eulerian bagi graf ini. Algoritma Hierholzer boleh digunakan.

Penyelesaian:

Kita boleh mendekatinya sebagai masalah Laluan Eulerian dalam teori graf. Dalam kes ini, pasangan boleh dianggap sebagai tepi, dan nilai dalam pasangan (permulaan dan akhir) boleh dianggap sebagai nod. Kita perlu mencari laluan Eulerian, iaitu laluan yang menggunakan setiap tepi tepat sekali, dan hujung satu tepi mesti sepadan dengan permulaan tepi seterusnya.

Langkah Utama:

1. Perwakilan Graf: Setiap nombor unik dalam pasangan akan menjadi nod dan setiap pasangan akan menjadi tepi dari mula[i] hingga akhir[i].
2. Kriteria Laluan Eulerian:
   • Laluan Eulerian wujud jika terdapat betul-betul dua nod dengan darjah ganjil, dan selebihnya mesti mempunyai darjah genap.
   • Kita perlu memastikan bahawa graf disambungkan (walaupun ini dijamin oleh pernyataan masalah).
3. Algoritma Hierholzer: Algoritma ini boleh digunakan untuk mencari laluan Eulerian. Ia melibatkan:
   • Bermula pada nod dengan darjah ganjil (jika ada).
   • Melintasi tepi, menandakan mereka sebagai dilawati.
   • Jika nod dicapai dengan tepi yang tidak digunakan, teruskan melintasi sehingga semua tepi digunakan.

Pelan:

• Bina graf menggunakan peta cincang untuk menyimpan senarai bersebelahan (setiap nod dan nod bersambungnya).
• Jejaki darjah (darjah dalam dan darjah luar) setiap nod.
• Gunakan algoritma Hierholzer untuk mencari laluan Eulerian.

Mari laksanakan penyelesaian ini dalam PHP: 2097. Susunan Pasangan yang Sah

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




</p>
<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>Pembinaan Graf</strong>:</p>

<ul>
<li>Kami membina graf menggunakan senarai bersebelahan dengan setiap kekunci ialah nod permulaan dan nilainya ialah senarai nod akhir.</li>
<li>Kami juga mengekalkan darjah keluar dan dalam darjah untuk setiap nod, yang akan membantu kami mencari nod permulaan untuk laluan Eulerian.</li>
</ul>
</li>
<li>
<p><strong>Mencari Nod Mula</strong>:</p>

<ul>
<li>Laluan Eulerian bermula pada nod di mana darjah keluar lebih besar daripada dalam darjah sebanyak 1 (jika nod sedemikian wujud).</li>
<li>Jika tiada nod sedemikian wujud, graf adalah seimbang dan kita boleh bermula pada mana-mana nod.</li>
</ul>
</li>
<li>
<p><strong>Algoritma Hierholzer</strong>:</p>

<ul>
<li>Kami bermula dari startNode dan berulang kali mengikut tepi, menandakannya sebagai dilawati dengan mengalih keluarnya daripada senarai bersebelahan.</li>
<li>Sebaik sahaja kami mencapai nod tanpa lagi tepi keluar, kami berundur dan membina hasilnya.</li>
</ul>
</li>
<li>
<p><strong>Kembalikan Keputusan</strong>:</p>
<ul>
<li>Hasilnya dibina dalam susunan terbalik kerana cara kita berundur, jadi kita membalikkannya pada penghujungnya.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Contoh Output:
</h3>



<pre class="brush:php;toolbar:false"><?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]]
?>

Kerumitan Masa:

• Membina graf: O(n), dengan n ialah bilangan pasangan.
• Algoritma Hierholzer: O(n), kerana setiap tepi dilawati sekali.
• Kerumitan Masa Keseluruhan: O(n).

Pendekatan ini cekap mencari susunan pasangan yang sah dengan menganggap masalah sebagai masalah laluan Eulerian dalam graf berarah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Susunan Pasangan yang Sah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!