Padamkan Nod Daripada Senarai Terpaut Hadir dalam Tatasusunan

3217. Padamkan Nod Daripada Senarai Terpaut Hadir dalam Tatasusunan

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Senarai Terpaut

Anda diberi tatasusunan nombor integer dan ketua senarai terpaut. Kembalikan kepala senarai terpaut yang diubah suai selepas mengalih keluar semua nod daripada senarai terpaut yang mempunyai nilai yang wujud dalam nums.

Contoh 1:

• Input: nombor = [1,2,3], kepala = [1,2,3,4,5]
• Output: [4,5]
• Penjelasan: Alih keluar nod dengan nilai 1, 2 dan 3.

Contoh 2:

• Input: Input: nums = [1], head = [1,2,1,2,1,2]
• Output: [2,2,2]
• Penjelasan: Keluarkan nod dengan nilai 1.

Contoh 3:

• Input: nombor = [5], kepala = [1,2,3,4]
• Output: [1,2,3,4] Tiada nod mempunyai nilai 5.

Kekangan:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵
• Semua elemen dalam nombor adalah unik.
• Bilangan nod dalam senarai yang diberikan adalah dalam julat [1, 10⁵].
• 1 <= Node.val <= 10⁵
• Input dijana sedemikian rupa sehingga terdapat sekurang-kurangnya satu nod dalam senarai terpaut yang mempunyai nilai yang tidak terdapat dalam nombor.

Petunjuk:

1. Tambah semua elemen nombor ke dalam Set.
2. Imbas senarai untuk menyemak sama ada elemen semasa perlu dipadamkan dengan menyemak Set.

Penyelesaian:

Kita perlu merentasi senarai terpaut dan mengalih keluar sebarang nod yang mempunyai nilai yang terdapat dalam nombor tatasusunan.

Pendekatan:

1. Set Cincang untuk Carian Pantas: Memandangkan menyemak sama ada nilai wujud dalam nums perlu cekap, kami akan menukar nombor kepada set cincang. Ini membenarkan carian O(1) untuk setiap nilai.
2. Lelaran Melalui Senarai Terpaut: Kami akan melelar melalui senarai terpaut dan mengalih keluar nod yang nilainya terdapat dalam set cincang.
3. Manipulasi Penunjuk: Semasa mengulang, kami akan melaraskan penunjuk untuk "langkau" nod yang sepadan dengan nilai dalam tatasusunan nums.

Langkah-langkah:

1. Tukar nombor kepada set cincang untuk carian O(1).
2. Lintas senarai terpaut dengan dua penunjuk: satu untuk nod semasa dan satu untuk nod sebelumnya untuk membantu mengalih keluar nod dengan cekap.
3. Untuk setiap nod, semak sama ada nilainya berada dalam set cincang. Jika ya, kemas kini nod sebelumnya di sebelah untuk melangkau nod semasa.

Mari laksanakan penyelesaian ini dalam PHP: 3217. Padamkan Nod Daripada Senarai Terpaut Hadir dalam Tatasusunan

val = $val;
        $this->next = $next;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @param ListNode $head
     * @return ListNode
     */
    function removeElements($head, $nums) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

// Example usage:

// Linked List: 1 -> 2 -> 3 -> 4 -> 5
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

// Array nums: [1, 2, 3]
$nums = [1, 2, 3];

$solution = new Solution();
$result = $solution->removeElements($head, $nums);

// Function to print the linked list
function printList($node) {
    while ($node !== null) {
        echo $node->val . " ";
        $node = $node->next;
    }
}

// Print the resulting linked list
printList($result); // Output: 4 5
?>





  
  
  Penjelasan:




removeElements($head, $nums):


Kami mula-mula menukar nombor kepada set cincang ($numSet = array_flip($nums);) untuk carian pantas.
Nod tiruan dibuat dan dipautkan ke kepala senarai. Ini membantu memudahkan kes tepi seperti mengeluarkan nod kepala.
Penunjuk sebelumnya menjejaki nod sebelum yang semasa, membolehkan kami mengalih keluar nod semasa dengan melangkaunya dalam senarai.
Untuk setiap nod, kami menyemak sama ada nilainya dalam numSet. Jika ya, kami mengalih keluarnya dengan melaraskan penuding sebelumnya->seterusnya untuk melangkau nod semasa.



Kes Tepi:


Jika nod kepala perlu dialih keluar, nod tiruan memastikan kepala boleh dikeluarkan dengan bersih dan masih mengembalikan senarai yang betul.
Mengendalikan kes di mana berbilang nod berturut-turut perlu dialih keluar.



Kerumitan:



Kerumitan Masa: O(n), dengan n ialah bilangan nod dalam senarai terpaut. Kami melawat setiap nod sekali. Menukar nombor kepada set memerlukan O(m), dengan m ialah saiz nombor.

Kerumitan Ruang: O(m) untuk menyimpan set nombor.





  
  
  Contoh Panduan:


Untuk nombor input = [1, 2, 3] dan kepala = [1, 2, 3, 4, 5], algoritma akan:


Mulakan pada nod 1, semak sama ada 1 dalam nombor, dan alih keluarnya.
Alih ke nod 2, semak sama ada 2 dalam nombor, dan alih keluarnya.
Alih ke nod 3, semak sama ada 3 dalam nombor, dan alih keluarnya.
Alih ke nod 4 dan 5, yang tiada dalam nombor, supaya mereka kekal dalam senarai.


Senarai terpaut yang terhasil ialah [4, 5].
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 Padamkan Nod Daripada Senarai Terpaut Hadir dalam Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!