Penamat Tatasusunan Minimum

3133. Penamat Tatasusunan Minimum

Kesukaran: Sederhana

Topik: Manipulasi Bit

Anda diberi dua integer n dan x. Anda perlu membina tatasusunan positif nombor integer saiz n di mana untuk setiap 0 <= i < n - 1, nums[i 1] ialah lebih besar daripada nums[i], dan hasil operasi bitwise AND antara semua elemen nums ialah x.

Kembalikan nilai minimum yang mungkin bagi nombor[n - 1].

Contoh 1:

• Input: n = 3, x = 4
• Output: 6
• Penjelasan: nombor boleh menjadi [4,5,6] dan elemen terakhirnya ialah 6.

Contoh 2:

• Input: n = 2, x = 7
• Output: 15
• Penjelasan: nombor boleh menjadi [7,15] dan elemen terakhirnya ialah 15.

Contoh 3:

• Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Output: 10

Kekangan:

• 1 <= n, x <= 10⁸

Petunjuk:

1. Setiap elemen tatasusunan hendaklah diperoleh dengan “mencantumkan” x dan v dengan v = 0, 1, 2, …(n - 1).
2. Untuk menggabungkan x dengan nombor v yang lain, pastikan bit set x tidak disentuh, untuk semua bit lain, isikan bit set v dari kanan ke kiri mengikut urutan satu demi satu.
3. Jadi jawapan akhir ialah “gabungan” bagi x dan n - 1.

Penyelesaian:

Kita perlu membina nombor tatasusunan bilangan bulat positif saiz n, di mana setiap elemen berturut-turut adalah lebih besar daripada sebelumnya. Bitwise AND semua elemen dalam nums harus menghasilkan x. Kami diminta untuk mencari nilai minimum yang mungkin bagi nums[n-1].

Berikut ialah pecahan:

1. Bit Manipulation Insight: Kita boleh perhatikan bahawa nums[i] harus dibina dengan menggabungkan x dengan integer 0, 1, ..., n-1. Ini akan membantu memastikan hasil bitwise AND menghasilkan x kerana kita bermula dengan asas x.

2. Membina Elemen Tatasusunan: Setiap elemen boleh dianggap sebagai x digabungkan dengan beberapa integer, dan kami menyasarkan untuk memastikan bit x kekal utuh. Kami mengisi bit tambahan daripada integer untuk mendapatkan nombor yang semakin meningkat sambil mengekalkan hasil AND sebagai x.

3. Strategi Penggabungan: Untuk mencari nombor minimum[n-1], kita hanya perlu menggabungkan x dengan n-1. Penggabungan dalam konteks ini bermakna jika sebarang bit dalam x ialah 1, ia kekal 1. Kami menggunakan bit daripada n-1 untuk menambah sebarang bit tambahan yang diperlukan tanpa mengubah bit yang ditetapkan dalam x.

Mari laksanakan penyelesaian ini dalam PHP: 3133. Penamat Tatasusunan Minimum

  
  
  Penjelasan:




Pemeriksaan Bit dan Tetapan:


Kami menyemak setiap bit ans (bermula dari x), dan jika bit adalah 0 dalam ans, kami melihat kepada bit yang sepadan dalam k (iaitu n-1).
Jika bit dalam k ialah 1, kami menetapkan bit dalam ans kepada 1. Proses ini memastikan kenaikan minimum dalam nilai sambil mengekalkan bit yang ditetapkan dalam x.



Kekangan Gelung:


Kami mengulangi setiap kedudukan bit sehingga maksimum yang dikira (kMaxBit), memastikan kami meliputi bit yang diperlukan daripada kedua-dua x dan n.



Keputusan:


Nilai akhir ans ialah nilai minimum yang mungkin untuk nums[n-1] yang memenuhi syarat.





  
  
  Kerumitan:



Algoritma beroperasi dalam masa tetap kerana bilangan bit dalam mana-mana integer dalam julat ini dihadkan dengan 32, menjadikan pendekatan ini cekap walaupun untuk nilai n dan x yang besar.


Penyelesaian ini menghasilkan angka minimum yang diingini[n-1] sambil mengekalkan sifat yang diperlukan.

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 Penamat Tatasusunan Minimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!