Gabungan Terbesar Dengan Bitwise DAN Lebih Besar Daripada Sifar

2275. Gabungan Terbesar Dengan Bitwise DAN Lebih Besar Daripada Sifar

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Manipulasi Bit, Mengira

bitwise AND nombor tatasusunan ialah bitwise DAN semua integer dalam nombor.

• Sebagai contoh, untuk nums = [1, 5, 3], bitwise AND bersamaan dengan 1 & 5 & 3 = 1.
• Selain itu, untuk nums = [7], bitwise AND ialah 7.

Anda diberi pelbagai calon integer positif. Nilaikan bitwise DAN setiap gabungan bilangan calon. Setiap nombor dalam calon hanya boleh digunakan sekali dalam setiap gabungan.

Kembalikan saiz gabungan terbesar calon dengan bitwise DAN lebih besar daripada 0.

Contoh 1:

• Input: calon = [16,17,71,62,12,24,14]
• Output: 4
• Penjelasan: Gabungan [16,17,62,24] mempunyai bitwise AND daripada 16 & 17 & 62 & 24 = 16 > 0.
  • Saiz gabungan ialah 4.
  • Ia boleh ditunjukkan bahawa tiada kombinasi dengan saiz lebih besar daripada 4 mempunyai bitwise DAN lebih besar daripada 0.
  • Perhatikan bahawa lebih daripada satu kombinasi mungkin mempunyai saiz yang paling besar.
  • Sebagai contoh, gabungan [62,12,24,14] mempunyai bitwise AND daripada 62 & 12 & 24 & 14 = 8 > 0.

Contoh 2:

• Input: calon = [8,8]
• Output: 2
• Penjelasan: Gabungan terbesar [8,8] mempunyai bitwise AND daripada 8 & 8 = 8 > 0.
  • Saiz gabungan ialah 2, jadi kami kembalikan 2.

Kekangan:

• 1 <= candidates.length <= 10⁵
• 1 <= calon[i] <= 10⁷

Petunjuk:

1. Untuk bitwise DAN lebih besar daripada sifar, sekurang-kurangnya satu bit hendaklah 1 untuk setiap nombor dalam gabungan.
2. Calon adalah 24 bit panjang, jadi untuk setiap kedudukan bit, kita boleh mengira saiz gabungan terbesar supaya bitwise DAN akan mempunyai 1 pada kedudukan bit itu.

Penyelesaian:

Kita perlu menumpukan pada mengenal pasti kumpulan nombor di mana sekurang-kurangnya satu kedudukan bit dalam perwakilan binari mereka kekal ditetapkan (1) merentas semua nombor dalam gabungan.

Rangka Penyelesaian

1. Analisis Bit: Memandangkan setiap nombor dalam calon boleh diwakili oleh nombor binari dengan sehingga 24 bit (sebagai 1 <= calon[i] <= 10^7), kita hanya perlu meneliti setiap kedudukan bit dari 0 hingga 23.

2. Kira Set Bit pada Setiap Kedudukan: Untuk setiap kedudukan bit, kira bilangan nombor dalam calon yang bit itu ditetapkan kepada 1. Jika berbilang nombor berkongsi sedikit dalam kedudukan yang sama, mereka boleh berpotensi membentuk gabungan dengan bitwise DAN lebih besar daripada sifar pada kedudukan bit itu.

3. Cari Kiraan Terbesar: Bilangan nombor terbesar dengan bit set pada mana-mana kedudukan tertentu akan menjadi jawapannya, kerana ia mewakili gabungan terbesar yang mungkin di mana keputusan bit DAN lebih besar daripada sifar.

Contoh

Pertimbangkan calon = [16, 17, 71, 62, 12, 24, 14]:

• Tukar setiap nombor kepada binari dan analisis kedudukan bit.
• Kira berapa kali setiap bit ditetapkan merentas semua nombor.
• Cari kiraan maksimum merentas semua kedudukan bit.

Mari laksanakan penyelesaian ini dalam PHP: 2275. Gabungan Terbesar Dengan Bitwise DAN Lebih Besar Daripada Sifar

  
  
  Penjelasan:




Gelung Melalui Setiap Kedudukan Bit: Kami mengulangi setiap kedudukan bit dari 0 hingga 23.

Kira Nombor dengan Set Bit: Untuk setiap kedudukan, kira bilangan nombor dalam calon yang mempunyai set bit tertentu itu.

Kemas kini Saiz Gabungan Maksimum: Jejaki kiraan tertinggi merentas semua kedudukan bit.

Kembalikan Hasil: Hasilnya ialah saiz gabungan terbesar dengan bitwise DAN lebih besar daripada sifar, seperti yang diperlukan.



  
  
  Analisis Kerumitan




Kerumitan Masa: O(n x 24) = O(n), dengan n ialah bilangan elemen dalam calon, kerana kami melakukan 24 operasi (satu untuk setiap kedudukan bit) untuk setiap nombor.

Kerumitan Angkasa: O(1), kerana kami hanya menggunakan jumlah ruang tambahan yang tetap.


Pendekatan ini cukup cekap untuk mengendalikan had saiz input (calon.panjang <= 105).

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 Gabungan Terbesar Dengan Bitwise DAN Lebih Besar Daripada Sifar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!