Subarray Terpanjang Dengan Bitwise Maksimum DAN

2419. Subarray Terpanjang Dengan Bitwise Maksimum DAN

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Penguat otak

Anda diberi nombor tatasusunan integer bersaiz n.

Pertimbangkan tidak kosong subbaris daripada nombor yang mempunyai maksimum yang mungkin bitwise DAN.

• Dalam erti kata lain, biarkan k ialah nilai maksimum bagi bitwise DAN daripada sebarang subbaris nombor. Kemudian, hanya subarray dengan bitwise DAN sama dengan k perlu dipertimbangkan.

Kembalikan panjang terpanjang subbaris sedemikian.

Bitwise AND bagi tatasusunan ialah bitwise DAN semua nombor di dalamnya.

subarray ialah jujukan unsur bersebelahan dalam tatasusunan.

Contoh 1:

• Input: nombor = [1,2,3,3,2,2]
• Output: 2
• Penjelasan:
  • Maksimum bitwise AND bagi subarray ialah 3.
  • Subarray terpanjang dengan nilai itu ialah [3,3], jadi kami kembalikan 2.

Contoh 2:

• Input: nombor = [1,2,3,4]
• Output: 1
• Penjelasan:
  • Maksimum bitwise AND bagi subarray ialah 4.
  • Subarray terpanjang dengan nilai itu ialah [4], jadi kami mengembalikan 1.

Kekangan:

• 1 <= nums.length <= 10¹
• 1 <= nums[i] <= 10⁶

Petunjuk:

1. Perhatikan bahawa bitwise DAN dua nombor berbeza akan sentiasa kurang daripada maksimum dua nombor tersebut.
2. Apakah yang memberitahu kita tentang sifat subarray yang harus kita pilih?

Penyelesaian:

Mari kita pecahkan dulu masalah ini langkah demi langkah:

Wawasan Utama:

1. Bitwise DAN Sifat:

   • Bitwise AND bagi dua nombor biasanya lebih kecil daripada atau sama dengan kedua-dua nombor.
   • Oleh itu, jika kita menemui nilai maksimum dalam tatasusunan, subarray yang akan mencapai bitwise maksimum ini DAN nilai mesti terdiri daripada nilai maksimum ini berulang.

2. Objektif:

   • Cari nilai maksimum dalam tatasusunan.
   • Cari subarray bersebelahan terpanjang bagi nilai maksimum itu, kerana mana-mana nombor lain dalam subarray akan mengurangkan keseluruhan bitwise AND hasil.

Pelan:

1. Lintas tatasusunan dan tentukan nilai maksimum.
2. Lintas tatasusunan sekali lagi untuk mencari subarray bersebelahan terpanjang di mana semua elemen adalah sama dengan nilai maksimum ini.

Contoh:

Untuk tatasusunan input [1,2,3,3,2,2], nilai maksimum ialah 3. Subarray bersebelahan terpanjang dengan hanya 3s ialah [3,3], yang mempunyai panjang 2.

Mari laksanakan penyelesaian ini dalam PHP: 2419. Subarray Terpanjang Dengan Bitwise Maksimum DAN

  
  
  Penjelasan:




Langkah 1: Kami mula-mula mencari nilai maksimum dalam tatasusunan menggunakan fungsi max() terbina dalam PHP.

Langkah 2: Kami memulakan dua pembolehubah, $maxLength untuk menyimpan panjang subarray terpanjang dan $currentLength untuk menjejak panjang subarray bersempadan semasa bagi nilai maksimum.

Langkah 3: Kami mengulangi tatasusunan:


Jika nombor semasa bersamaan dengan nilai maksimum, kami menambah panjang subarray semasa.
Jika nombor semasa tidak bersamaan dengan nilai maksimum, kami menyemak sama ada subarray semasa adalah yang paling lama setakat ini dan menetapkan semula panjangnya.



Langkah Terakhir: Selepas gelung, kami memastikan bahawa jika subarray terpanjang berada di penghujung tatasusunan, kami masih menganggapnya.
Akhir sekali, kami mengembalikan panjang subarray terpanjang yang mengandungi hanya nilai maksimum.



  
  
  Kerumitan Masa:



Mencari nilai maksimum yang diperlukan (O(n)).
Merentasi tatasusunan untuk mencari subarray terpanjang yang diperlukan (O(n)).
Kerumitan masa keseluruhan: (O(n)), dengan (n) ialah panjang tatasusunan.



  
  
  Kes Ujian:


Untuk input [1, 2, 3, 3, 2, 2], output ialah 2 dan untuk [1, 2, 3, 4], output ialah 1, seperti yang dijangkakan.

Penyelesaian ini mengendalikan kekangan dan menyelesaikan masalah dengan cekap.

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 Subarray Terpanjang Dengan Bitwise Maksimum DAN. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!