Kira Bilangan Subset Bitwise-OR Maksimum

2044. Kira Bilangan Subset Bitwise-OR Maksimum

Kesukaran: Sederhana

Topik: Tatasusunan, Menjejak Belakang, Manipulasi Bit, Penghitungan

Memandangkan nombor tatasusunan integer, cari maksimum yang mungkin bitwise ATAU subset nombor dan kembalikan nombor bilangan subset bukan kosong yang berbeza dengan bitwise maksimum ATAU.

Suatu tatasusunan a ialah subset tatasusunan b jika a boleh diperolehi daripada b dengan memadamkan beberapa (mungkin sifar) unsur b. Dua subset dianggap berbeza jika indeks unsur yang dipilih adalah berbeza.

Bitwise OR tatasusunan a adalah sama dengan a[0] OR a[1] OR ... ATAU a[a.length - 1] (0-diindeks).

Contoh 1:

• Input: nombor = [3,1]
• Output: 2
• Penjelasan: Bitwise ATAU maksimum yang mungkin bagi subset ialah 3. Terdapat 2 subset dengan bitwise ATAU daripada 3:
  • [3]
  • [3,1]

Contoh 2:

• Input: nombor = [2,2,2]
• Output: 7
• Penjelasan: Semua subset bukan kosong bagi [2,2,2] mempunyai bitwise OR daripada 2. Terdapat 23 - 1 = 7 jumlah subset.

Contoh 3:

• Input: nombor = [3,2,1,5]
• Output: 6
• Penjelasan: Bitwise ATAU maksimum yang mungkin bagi subset ialah 7. Terdapat 6 subset dengan bitwise ATAU daripada 7:
  • [3,5]
  • [3,1,5]
  • [3,2,5]
  • [3,2,1,5]
  • [2,5]
  • [2,1,5]

Kekangan:

• 1
• 1 5

Petunjuk:

1. Bolehkah kita menghitung semua subset yang mungkin?
2. Maksimum bitwise-OR ialah bitwise-OR bagi keseluruhan tatasusunan.

Penyelesaian:

Kita boleh ikut langkah ini:

1. Kira Bitwise Maksimum OR: Bitwise OR maksimum subset boleh ditentukan dengan melakukan operasi OR bitwise merentas semua elemen tatasusunan. Ini memberikan kita bitwise maksimum yang mungkin ATAU.

2. Enumerate All Subsets: Memandangkan saiz array adalah kecil (sehingga 16), kita boleh menghitung semua subset yang mungkin menggunakan teknik manipulasi bit. Untuk tatasusunan saiz n, terdapat 2^n subset yang mungkin.

3. Kira Subset Sah: Untuk setiap subset, hitung bitwise ATAU dan semak sama ada ia sepadan dengan bitwise maksimum ATAU. Jika ya, tambahkan pembilang.

Mari laksanakan penyelesaian ini dalam PHP: 2044. Kira Bilangan Subset Bitwise-OR Maksimum

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function countMaxBitwiseORSubsets($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3, 1];
echo countMaxBitwiseORSubsets($nums1) . "\n"; // Output: 2

$nums2 = [2, 2, 2];
echo countMaxBitwiseORSubsets($nums2) . "\n"; // Output: 7

$nums3 = [3, 2, 1, 5];
echo countMaxBitwiseORSubsets($nums3) . "\n"; // Output: 6
?>

Penjelasan:

1. Maksimum Bitwise ATAU Pengiraan:

   • Kami menggunakan gelung untuk mengira bitwise OR maksimum tatasusunan dengan melakukan OR bitwise pada setiap elemen.

2. Penghitungan Subset:

   • Kami menggelungkan semua nombor dari 1 hingga 2^n - 1 (dengan n ialah panjang nombor), mewakili semua subset bukan kosong.
   • Untuk setiap nombor, kami menyemak setiap bit untuk melihat elemen yang disertakan dalam subset.

3. Kiraan Subset yang Sah:

   • Selepas mengira bitwise ATAU untuk subset semasa, kami menyemak sama ada ia sama dengan maxOR. Jika ya, kami menambah kaunter kami.

Penyelesaian ini cekap memandangkan kekangan dan harus berfungsi dengan baik untuk tatasusunan bersaiz sehingga 16, menghasilkan paling banyak 65,535 subset untuk dinilai.

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 Kira Bilangan Subset Bitwise-OR Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!