Längstes Subarray mit maximalem bitweisen UND

2419. Längstes Subarray mit maximalem bitweisen UND

Schwierigkeit:Mittel

Themen: Array, Bit-Manipulation, Brainteaser

Sie erhalten ein ganzzahliges Array mit der Größe n.

Betrachten Sie ein nicht leeres Subarray aus Nums, das das maximal mögliche bitweise UND aufweist.

• Mit anderen Worten, sei k der Maximalwert des bitweisen UND von jedem Subarray von Zahlen. Dann sollten nur Subarrays mit einem bitweisen AND gleich k berücksichtigt werden.

Gibt die Länge des längstensolchen Subarrays zurück.

Das bitweise UND eines Arrays ist das bitweise UND aller darin enthaltenen Zahlen.

Ein Subarray ist eine zusammenhängende Folge von Elementen innerhalb eines Arrays.

Beispiel 1:

• Eingabe: nums = [1,2,3,3,2,2]
• Ausgabe: 2
• Erklärung:
  • Das maximal mögliche bitweise UND eines Subarrays beträgt 3.
  • Das längste Subarray mit diesem Wert ist [3,3], also geben wir 2 zurück.

Beispiel 2:

• Eingabe: nums = [1,2,3,4]
• Ausgabe: 1
• Erklärung:
  • Das maximal mögliche bitweise UND eines Subarrays beträgt 4.
  • Das längste Subarray mit diesem Wert ist [4], also geben wir 1 zurück.

Einschränkungen:

• 1 <= nums.length <= 10¹
• 1 <= nums[i] <= 10⁶

Hinweis:

1. Beachten Sie, dass das bitweise UND zweier verschiedener Zahlen immer strikt kleiner als das Maximum dieser beiden Zahlen sein wird.
2. Was sagt uns das über die Art des Subarrays, das wir wählen sollten?

Lösung:

Lassen Sie uns das Problem zunächst Schritt für Schritt aufschlüsseln:

Wichtige Erkenntnisse:

1. Bitweise UND-Eigenschaften:

   • Das bitweise UND zweier Zahlen ist im Allgemeinen kleiner oder gleich beiden Zahlen.
   • Wenn wir also einen Maximalwert im Array finden, muss das Subarray, das diesen maximalen bitweisen UND-Wert erreicht, aus diesem wiederholten Maximalwert bestehen.

2. Ziel:

   • Finden Sie den Maximalwert im Array.
   • Finden Sie das längste zusammenhängende Unterarray dieses Maximalwerts, da jede andere Zahl im Unterarray das gesamte bitweise UND-Ergebnis reduzieren würde.

Planen:

1. Durchlaufen Sie das Array und bestimmen Sie den Maximalwert.
2. Durchlaufen Sie das Array erneut, um das längste zusammenhängende Unterarray zu finden, in dem alle Elemente diesem Maximalwert entsprechen.

Beispiel:

Für das Eingabearray [1,2,3,3,2,2] beträgt der Maximalwert 3. Das längste zusammenhängende Unterarray mit nur 3 ist [3,3] mit einer Länge von 2.

Lassen Sie uns diese Lösung in PHP implementieren: 2419. Längstes Subarray mit maximalem bitweisen AND

  
  
  Erläuterung:




Schritt 1: Wir ermitteln zunächst den Maximalwert im Array mithilfe der in PHP integrierten Funktion max().

Schritt 2: Wir initialisieren zwei Variablen, $maxLength, um die Länge des längsten Subarrays zu speichern, und $currentLength, um die Länge des aktuellen zusammenhängenden Subarrays mit dem Maximalwert zu verfolgen.

Schritt 3: Wir durchlaufen das Array:


Wenn die aktuelle Zahl dem Maximalwert entspricht, erhöhen wir die Länge des aktuellen Subarrays.
Wenn die aktuelle Zahl nicht dem Maximalwert entspricht, prüfen wir, ob das aktuelle Subarray das bisher längste ist und setzen die Länge zurück.



Letzter Schritt: Nach der Schleife stellen wir sicher, dass wir es trotzdem berücksichtigen, wenn sich das längste Subarray am Ende des Arrays befindet.
Schließlich geben wir die Länge des längsten Subarrays zurück, das nur den Maximalwert enthält.



  
  
  Zeitkomplexität:



Das Finden des Maximalwerts erfordert (O(n)).
Das Durchlaufen des Arrays, um das längste Subarray zu finden, dauert (O(n)).
Gesamtzeitkomplexität: (O(n)), wobei (n) die Länge des Arrays ist.



  
  
  Testfälle:


Für die Eingabe [1, 2, 3, 3, 2, 2] ist die Ausgabe 2, und für [1, 2, 3, 4] ist die Ausgabe wie erwartet 1.

Diese Lösung bewältigt die Einschränkungen und löst das Problem effizient.

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 vonLängstes Subarray mit maximalem bitweisen UND. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!