Subarray Terpendek Dengan ATAU Sekurang-kurangnya K II

3097. Subarray Terpendek Dengan ATAU Sekurang-kurangnya K II

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Tetingkap Gelongsor

Anda diberi nombor tatasusunan bukan negatif integer dan integer k.

Suatu tatasusunan dipanggil istimewa jika bitwise ATAU semua elemennya ialah sekurang-kurangnya k.

Kembalikan panjang subarray khas terpendek tidak kosong¹ nombor, atau pulangkan -1 jika tiada subbaris khas wujud.

Contoh 1:

• Input: nombor = [1,2,3], k = 2
• Output: 1
• Penjelasan: Subarray [3] mempunyai nilai ATAU 3. Oleh itu, kami mengembalikan 1.

Contoh 2:

• Input: nombor = [2,1,8], k = 10
• Output: 3
• Penjelasan: Subarray [2,1,8] mempunyai nilai ATAU 11. Oleh itu, kami mengembalikan 3.

Contoh 3:

• Input: nombor = [1,2], k = 0
• Output: 1
• Penjelasan: Subarray [1] mempunyai nilai ATAU 1. Oleh itu, kami mengembalikan 1.

Kekangan:

• 1 <= nums.length <= 2 * 10⁵
• 0 <= angka[i] <= 10⁹
• 0 <= k <= 10⁹

Petunjuk:

1. Untuk setiap nombor[i], kami boleh mengekalkan setiap subarray bitwise ATAU hasil yang berakhir dengannya.
2. Sifat bitwise OR ialah ia tidak pernah menyahset sebarang bit dan hanya menetapkan bit baharu
3. Jadi bilangan hasil yang berbeza untuk setiap nombor[i] adalah paling banyak bilangan bit 32.

Penyelesaian:

Kita boleh menggunakan pendekatan tetingkap gelongsor digabungkan dengan manipulasi bit untuk menjejaki ATAU elemen dalam tetingkap.

Pelan:

1. Pendekatan Tetingkap Gelongsor: Lelaran ke atas tatasusunan menggunakan dua penunjuk, mengekalkan subarray yang nilai ORnya ditandakan.
2. Bitwise OR: Operasi OR mengumpul nilai. Ia tidak pernah mengurangkan hasil (iaitu, apabila bit ditetapkan kepada 1, ia tidak boleh dinyahset). Ini bermakna semasa kita memanjangkan tetingkap, nilai OR hanya meningkat atau kekal sama.
3. Kecekapan: Kita boleh menggunakan deque (barisan dua hujung) untuk mengekalkan indeks subarray. Ini membolehkan kami meluncurkan tetingkap dengan cekap sambil menjejaki panjang subarray minimum.

Langkah-langkah:

1. Lintas tatasusunan, untuk setiap elemen, kekalkan larian ATAU.
2. Untuk setiap elemen, semak sama ada ATAU melebihi atau sama dengan k. Jika ya, cuba kecilkan tingkap dari sebelah kiri.
3. Tingkap gelongsor harus dialihkan dengan cekap dengan menjejaki nilai OR dalam struktur deque untuk membolehkan masa yang berterusan meluncur dan mengecut.

Mari laksanakan penyelesaian ini dalam PHP: 3097. Subarray Terpendek Dengan ATAU Sekurang-kurangnya K II

minimumSubarrayLength($nums1, $k1) . "\n"; // Output: 1

$nums2 = [2, 1, 8];
$k2 = 10;
echo $solution->minimumSubarrayLength($nums2, $k2) . "\n"; // Output: 3

$nums3 = [1, 2];
$k3 = 0;
echo $solution->minimumSubarrayLength($nums3, $k3) . "\n"; // Output: 1
?>





  
  
  Penjelasan:




kaedah SubarrayLength minimum:


Mulakan ans kepada nilai tinggi yang mustahil ($n 1).
Gunakan dua penunjuk l (kiri) dan r (kanan) untuk mengembangkan dan mengecilkan tetingkap.
Kira OR subarray semasa anda mengembangkan tetingkap dengan orNum dan kurangkannya dengan undoOrNum apabila mengecut.
Apabila keputusan OR memenuhi atau melebihi k, semak sama ada saiz tetingkap semasa lebih kecil daripada ans.



Kaedah orNum dan undoOrNum:



kaedah orNum: Menambah bit pada kumulatif ATAU dengan mengemas kini tatasusunan kiraan. Jika bit baru ditetapkan dalam tetingkap (bermaksud kiraan[i] menjadi 1), bit itu ditambahkan pada ors.

kaedah undoOrNum: Mengeluarkan bit daripada kumulatif ATAU apabila menggelongsor tetingkap ke kiri. Jika bit tidak lagi ditetapkan dalam mana-mana nombor dalam tetingkap (bermaksud kiraan[i] menjadi 0), bit itu dikeluarkan daripada ors.



Kerumitan Masa:


Kerumitan masa ialah O(n) kerana setiap indeks ditambah dan dialih keluar daripada deque paling banyak sekali.

n ialah panjang tatasusunan input.




4*Kerumitan Masa*:


Kerumitan ruang ialah O(n) untuk menyimpan awalan ATAU tatasusunan dan deque.


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








Subarray : subarray ialah jujukan bukan kosong bersebelahan bagi elemen dalam tatasusunan. ↩





          

            
  

            
        
Atas ialah kandungan terperinci Subarray Terpendek Dengan ATAU Sekurang-kurangnya K II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!