XOR Maksimum untuk Setiap Pertanyaan

1829. XOR Maksimum untuk Setiap Pertanyaan

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Jumlah Awalan

Anda diberi diisih nombor tatasusunan bagi n integer bukan negatif dan integer maximumBit. Anda mahu melaksanakan pertanyaan berikut n kali:

• Cari integer bukan negatif k < 2^maximumBit supaya nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k ialah maksimum. k ialah jawapan kepada pertanyaan i^th.
• Alih keluar elemen terakhir daripada nombor tatasusunan semasa.

Kembalikan jawapan tatasusunan, dengan jawapan[i] ialah jawapan kepada pertanyaan i^ke.

Contoh 1:

• Input: nums = [0,1,1,3], maximumBit = 2
• Output: [0,3,2,3]
• Penjelasan: Pertanyaan dijawab seperti berikut:
  • 1^stpertanyaan pertama: nums = [0,1,1,3], k = 0 sejak 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
  • 2^nd pertanyaan: nums = [0,1,1], k = 3 sejak 0 XOR 1 XOR 1 XOR 3 = 3.
  • 3^rd pertanyaan: nums = [0,1], k = 2 sejak 0 XOR 1 XOR 2 = 3.
  • 4^th pertanyaan: nums = [0], k = 3 sejak 0 XOR 3 = 3.

Contoh 2:

• Input: nums = [2,3,4,7], maximumBit = 3
• Output: [5,2,6,5]
• Penjelasan: Pertanyaan dijawab seperti berikut:
  • 1^stpertanyaan pertama: nums = [2,3,4,7], k = 5 sejak 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
  • 2^nd pertanyaan: nums = [2,3,4], k = 2 sejak 2 XOR 3 XOR 4 XOR 2 = 7.
  • 3^rd pertanyaan: nums = [2,3], k = 6 sejak 2 XOR 3 XOR 6 = 7.
  • 4^th pertanyaan: nums = [2], k = 5 sejak 2 XOR 5 = 7.

Contoh 3:

• Input: nombor = [0,1,2,2,5,7], maksimumBit = 3
• Output: [4,3,6,4,6,7]

Kekangan:

• bilangan panjang == n
• 1 <= n <= 10⁵
• 1 <= maximumBit <= 20
• 0 <= angka[i] < 2^maksimumBit
• nums​​​ diisih dalam susunan menaik.

Petunjuk:

1. Perhatikan bahawa keputusan XOR maksimum yang mungkin adalah sentiasa 2^{(Bit maksimum) - 1}
2. Jadi jawapan untuk awalan ialah XOR awalan itu XORed dengan 2^{(maksimumBit)-1}

Penyelesaian:

Kita perlu mengira XOR unsur dalam tatasusunan dengan cekap dan memaksimumkan hasilnya menggunakan nilai k supaya k kurang daripada 2^maximumBit. Berikut ialah pendekatan untuk menyelesaikan masalah ini:

Pemerhatian dan Pendekatan

1. Memaksimumkan XOR:
   Nombor maksimum yang boleh kita XOR dengan sebarang jumlah awalan untuk bit maksimumBit ialah ( 2^{text{maximumBit}} - 1 ). Ini kerana XORing dengan nombor semua 1s (iaitu, 111...1 dalam binari) akan sentiasa memaksimumkan hasil.

2. Pengiraan XOR Awalan:
   Daripada mengira semula XOR untuk setiap pertanyaan, kita boleh mengekalkan XOR terkumpul untuk keseluruhan tatasusunan. Memandangkan XOR mempunyai sifat A XOR B XOR B = A, mengalih keluar elemen terakhir daripada tatasusunan boleh dicapai dengan XOR mengeluarkan elemen itu daripada XOR terkumpul.

3. Algoritma:

   • Kira XOR semua elemen dalam nombor pada mulanya. Jom panggil currentXOR ini.
   • Untuk setiap pertanyaan (dari yang terakhir hingga yang pertama):
     • Kira nilai optimum k untuk pertanyaan itu dengan XORing currentXOR dengan maxNum dengan maxNum = 2^maximumBit - 1.
     • Lampirkan k pada senarai keputusan.
     • Alih keluar elemen terakhir daripada nums dengan XORing keluar daripada currentXOR.
   • Senarai keputusan akan mengandungi jawapan dalam susunan terbalik, jadi terbalikkannya pada penghujungnya.

Mari laksanakan penyelesaian ini dalam PHP: 1829. XOR Maksimum untuk Setiap Pertanyaan

  
  
  Penjelasan:




Kira maxNum:



maxNum dikira sebagai 2^maximumBit - 1, iaitu nombor dengan semua 1 dalam binari untuk panjang bit yang ditentukan.



Pengiraan XOR Awal:


Kami XOR semua elemen dalam nombor untuk mendapatkan XOR terkumpul (XOR semasa), mewakili XOR semua nombor dalam tatasusunan.



Lelaran Ke Belakang:


Kami bermula dari elemen terakhir dalam nombor dan mengira XOR maksimum untuk setiap langkah:



currentXOR ^ maxNum memberikan k maksimum untuk keadaan semasa.
Lampirkan k untuk menjawab.


Kami kemudian XOR elemen terakhir nombor dengan currentXOR untuk "mengalihkannya" daripada jumlah XOR untuk lelaran seterusnya.



Kembalikan Jawapan:


Memandangkan kami memproses senarai secara terbalik, jawapan akan mengandungi nilai dalam susunan terbalik, jadi senarai akhir sudah disusun dengan betul untuk keperluan kami.





  
  
  Analisis Kerumitan




Kerumitan Masa: O(n), kerana kita mengira XOR awal dalam O(n) dan setiap pertanyaan diproses dalam masa yang tetap.

Kerumitan Angkasa: O(n), untuk menyimpan jawapan.


Kod ini cekap dan harus mengendalikan had atas kekangan dengan baik.

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 XOR Maksimum untuk Setiap Pertanyaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!