Bilangan Operasi Minimum untuk Isih Pokok Perduaan mengikut Tahap

2471. Bilangan Operasi Minimum untuk Isih Pokok Perduaan Mengikut Tahap

Kesukaran: Sederhana

Topik: Pokok, Keluasan Carian Pertama, Pokok Binari

Anda diberi akar pokok binari dengan nilai unik.

Dalam satu operasi, anda boleh memilih mana-mana dua nod pada tahap yang sama dan menukar nilainya.

Kembalikan bilangan operasi minimum yang diperlukan untuk menjadikan nilai pada setiap peringkat disusun dalam tertib yang semakin meningkat.

Tahap nod ialah bilangan tepi di sepanjang laluan antaranya dan nod akar.

Contoh 1:

• Input: punca = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• Output: 3
• Penjelasan:
  • Tukar 4 dan 3. Tahap ke-2 menjadi [3,4].
  • Tukar 7 dan 5. Tahap ke-3 menjadi [5,6,8,7].
  • Tukar 8 dan 7. Tahap ke-3 menjadi [5,6,7,8].
  • Kami menggunakan 3 operasi jadi kembalikan 3.
  • Boleh dibuktikan bahawa 3 adalah bilangan minimum operasi yang diperlukan.

Contoh 2:

• Input: akar = [1,3,2,7,6,5,4]
• Output: 3
• Penjelasan:
  • Tukar 3 dan 2. Tahap ke-2 menjadi [2,3].
  • Tukar 7 dan 4. Tahap ke-3 menjadi [4,6,5,7].
  • Tukar 6 dan 5. Tahap ke-3 menjadi [4,5,6,7].
  • Kami menggunakan 3 operasi jadi kembalikan 3.
  • Boleh dibuktikan bahawa 3 adalah bilangan minimum operasi yang diperlukan.

Contoh 3:

• Input: akar = [1,2,3,4,5,6]
• Output: 0
• Penjelasan: Setiap tahap sudah diisih mengikut urutan yang semakin meningkat jadi kembalikan 0.

Kekangan:

• Bilangan nod dalam pepohon adalah dalam julat [1, 10⁵].
• 1 5
• Semua nilai pokok adalah unik.

Petunjuk:

1. Kami boleh mengumpulkan tahap nilai demi tahap dan menyelesaikan setiap kumpulan secara bebas.
2. Lakukan BFS untuk mengumpulkan tahap nilai mengikut tahap.
3. Cari bilangan swap minimum untuk mengisih tatasusunan setiap peringkat.
4. Semasa mengulangi tatasusunan, semak elemen semasa, dan jika tidak dalam indeks yang betul, gantikan elemen itu dengan indeks elemen yang sepatutnya datang.

Penyelesaian:

Masalahnya ialah tentang mengisih nilai peringkat pokok binari mengikut tahap dalam susunan yang semakin meningkat dengan bilangan operasi minimum. Dalam setiap operasi, kita boleh menukar nilai dua nod yang berada pada tahap yang sama. Matlamatnya ialah untuk menentukan bilangan minimum operasi sedemikian yang diperlukan untuk mencapai susunan yang diisih.

Perkara Utama:

1. Tahap Pokok Perduaan: Setiap peringkat pepohon perduaan sepatutnya mempunyai nilai yang disusun mengikut susunan yang semakin meningkat.
2. Nilai Unik: Semua nod mempunyai nilai unik, memudahkan pengisihan kerana tiada pendua.
3. BFS untuk Pengumpulan Tahap: Gunakan Breadth-First Search (BFS) untuk merentasi pokok dan nod kumpulan mengikut tahapnya.
4. Pertukaran Minimum: Untuk setiap peringkat, kita perlu mencari bilangan swap minimum yang diperlukan untuk mengisih nilai nod pada tahap itu.
5. Kekangan: Pokok boleh mempunyai sehingga 10^5 nod, jadi penyelesaiannya mestilah cekap.

Pendekatan:

1. BFS Traversal: Lakukan BFS untuk melintasi pokok dan kumpulkan nilai nod pada setiap peringkat.
2. Isih Setiap Tahap: Untuk setiap tahap, kira bilangan minimum pertukaran untuk mengisih nilai dalam susunan yang semakin meningkat.
3. Penguraian Kitaran: Pemerhatian utama untuk meminimumkan swap ialah pengisihan tatasusunan boleh dilihat sebagai elemen pertukaran dalam kitaran. Bilangan pertukaran minimum untuk setiap kitaran unsur yang salah letak ialah panjang kitaran tolak satu.
4. Swap Terkumpul: Jumlahkan swap untuk setiap tahap untuk mendapatkan jumlah bilangan swap yang diperlukan.

Pelan:

1. BFS: Lintas pokok menggunakan BFS untuk mengumpul nod pada setiap peringkat.
2. Isih Setiap Tahap: Isih nilai pada setiap peringkat dan hitung bilangan minimum pertukaran.
3. Kira Pertukaran: Gunakan penguraian kitaran untuk mencari swap minimum yang diperlukan untuk mengisih nod pada setiap peringkat.

Mari laksanakan penyelesaian ini dalam PHP: 2471. Bilangan Operasi Minimum untuk Isih Pokok Perduaan mengikut Tahap

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Penjelasan:

1. Langkah 1: Lakukan BFS untuk mengumpulkan nod mengikut tahap:

   • Mulakan dari akar dan melintasi peringkat pokok mengikut tahap.
   • Untuk setiap nod, tambahkan nilainya pada tahap yang sepadan dalam tatasusunan tahap.

2. Langkah 2: Untuk setiap tahap, kira swap minimum untuk mengisih nilai:

   • Isih nilai pada setiap peringkat.
   • Gunakan pendekatan berasaskan kitaran untuk mengira swap minimum yang diperlukan untuk mengubah tahap semasa kepada tahap yang diisih.

3. Penguraian Kitaran:

   • Untuk setiap elemen yang tidak diisih, jejaki kitarannya (iaitu, ke mana ia harus pergi) dan tandai elemen sebagai dilawati.
   • Untuk setiap kitaran, bilangan swap yang diperlukan ialah panjang kitaran tolak satu.

4. Kembalikan jumlah bilangan swap:

   • Jumlah swap yang diperlukan untuk setiap peringkat dan pulangkan jumlahnya.

Contoh Panduan:

Contoh 1:

Pokok input:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Tahap:

• Tahap 0: [1]
• Tahap 1: [4, 3]
• Tahap 2: [7, 6, 8, 5]
• Tahap 3: [9, 10]

1. Tahap 1: [4, 3]

   • Isih kepada [3, 4] dengan 1 pertukaran (tukar 4 dan 3).

2. Tahap 2: [7, 6, 8, 5]

   • Isih kepada [5, 6, 7, 8] dengan 2 pertukaran (tukar 7 dan 5, tukar 8 dan 7).

3. Tahap 3: [9, 10]

   • Sudah diisih, tiada pertukaran diperlukan.

Jumlah pertukaran = 1 (Tahap 1) 2 (Tahap 2) = 3 pertukaran.

Output: 3

Contoh 2:

Pokok input:

        1
       / \
      4   3
     / \ / \
    7  6 8  5
             \
              9
               \
                10

Tahap:

• Tahap 0: [1]
• Tahap 1: [3, 2]
• Tahap 2: [7, 6, 5, 4]

1. Tahap 1: [3, 2]

   • Isih kepada [2, 3] dengan 1 pertukaran (tukar 3 dan 2).

2. Tahap 2: [7, 6, 5, 4]

   • Isih kepada [4, 5, 6, 7] dengan 2 pertukaran (tukar 7 dan 4, tukar 6 dan 5).

Jumlah pertukaran = 1 (Tahap 1) 2 (Tahap 2) = 3 pertukaran.

Output: 3

Kerumitan Masa:

1. BFS: O(N) dengan N ialah bilangan nod dalam pepohon.
2. Isih Setiap Tahap: Mengisih nilai pada setiap tahap mengambil masa O(L log L) di mana L adalah bilangan nod pada tahap semasa. Dalam kes yang paling teruk, jumlah kerumitan pengisihan ialah O(N log N).
3. Penguraian Kitaran: O(L) untuk setiap peringkat.

Oleh itu, kerumitan masa keseluruhan ialah O(N log N), yang cukup cekap memandangkan kekangan.

Output untuk Contoh:

Untuk pokok input:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Keluaran ialah 3 pertukaran, seperti yang diperincikan dalam contoh.

Penyelesaian ini dengan cekap mengira bilangan swap minimum yang diperlukan untuk mengisih setiap peringkat pepohon binari dengan menggunakan BFS untuk mengumpulkan nod mengikut tahap dan kitaran penguraian untuk meminimumkan bilangan swap. Kerumitan masa O(N log N) adalah optimum untuk mengendalikan pokok dengan sehingga 10^5 nod.

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 Bilangan Operasi Minimum untuk Isih Pokok Perduaan mengikut Tahap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!