Zählen Sie die Anzahl der maximalen bitweisen ODER-Teilmengen

2044. Zählen Sie die Anzahl der maximalen bitweisen ODER-Teilmengen

Schwierigkeit:Mittel

Themen: Array, Backtracking, Bitmanipulation, Enumeration

Suchen Sie bei einem gegebenen ganzzahligen Array nums das maximal mögliche bitweise ODER einer Teilmenge von nums und geben Sie die Anzahl verschiedener nicht leerer Teilmengen mit dem maximalen bitweisen ODER.

Ein Array a ist eine

Teilmenge eines Arrays b, wenn a aus b durch Löschen einiger (möglicherweise null) Elemente von b erhalten werden kann. Zwei Teilmengen gelten als unterschiedlich, wenn die Indizes der ausgewählten Elemente unterschiedlich sind.

Das bitweise ODER eines Arrays a ist gleich a[0] OR a[1] OR ... OR a[a.length - 1] (

0-indiziert).

Beispiel 1:

• Eingabe: nums = [3,1]
• Ausgabe: 2
• Erklärung: Das maximal mögliche bitweise ODER einer Teilmenge beträgt 3. Es gibt 2 Teilmengen mit einem bitweisen ODER von 3:
  [3]
  [3,1]

Beispiel 2:

• Eingabe: nums = [2,2,2]
• Ausgabe: 7
• Erklärung: Alle nicht leeren Teilmengen von [2,2,2] haben ein bitweises ODER von 2. Es gibt 23 - 1 = 7 Gesamtteilmengen.

Beispiel 3:

• Eingabe: nums = [3,2,1,5]
• Ausgabe: 6
• Erklärung: Das maximal mögliche bitweise ODER einer Teilmenge beträgt 7. Es gibt 6 Teilmengen mit einem bitweisen ODER von 7:
  [3,5]
  [3,1,5]
  [3,2,5]
  [3,2,1,5]
  [2,5]
  [2,1,5]

Einschränkungen:

1 1 5

Hinweis:

Können wir alle möglichen Teilmengen aufzählen?
Das maximale bitweise ODER ist das bitweise ODER des gesamten Arrays.

Lösung:

Wir können diesen Schritten folgen:

1. Berechnen Sie das maximale bitweise ODER: Das maximale bitweise ODER einer Teilmenge kann bestimmt werden, indem eine bitweise ODER-Operation über alle Elemente des Arrays durchgeführt wird. Dies gibt uns das maximal mögliche bitweise ODER.

2. Alle Teilmengen aufzählen: Da die Größe des Arrays klein ist (bis zu 16), können wir alle möglichen Teilmengen mithilfe einer Bitmanipulationstechnik aufzählen. Für ein Array der Größe n gibt es 2^n mögliche Teilmengen.

3. Gültige Teilmengen zählen: Berechnen Sie für jede Teilmenge ihr bitweises ODER und prüfen Sie, ob es mit dem maximalen bitweisen ODER übereinstimmt. Wenn dies der Fall ist, erhöhen Sie einen Zähler.

Lassen Sie uns diese Lösung in PHP implementieren: 2044. Zählen Sie die Anzahl der maximalen bitweisen ODER-Teilmengen

<?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
?>

Erläuterung:

1. Maximale bitweise ODER-Berechnung:

   • Wir verwenden eine Schleife, um das maximale bitweise ODER des Arrays zu berechnen, indem wir für jedes Element ein bitweises ODER durchführen.

2. Teilmengenaufzählung:

   • Wir durchlaufen alle Zahlen von 1 bis 2^n - 1 (wobei n die Länge von Zahlen ist) und repräsentieren alle nicht leeren Teilmengen.
   • Für jede Zahl prüfen wir jedes Bit, um zu sehen, welche Elemente in der Teilmenge enthalten sind.

3. Gültige Teilmengenanzahl:

   • Nachdem wir das bitweise ODER für die aktuelle Teilmenge berechnet haben, prüfen wir, ob es gleich maxOR ist. Wenn dies der Fall ist, erhöhen wir unseren Zähler.

Diese Lösung ist angesichts der Einschränkungen effizient und sollte für Arrays mit einer Größe von bis zu 16 gut funktionieren, sodass höchstens 65.535 Teilmengen ausgewertet werden müssen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der maximalen bitweisen ODER-Teilmengen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!