Spalten umdrehen, um die maximale Anzahl gleicher Zeilen zu erreichen

1072. Spalten umdrehen, um die maximale Anzahl gleicher Zeilen zu erreichen

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Matrix

Sie erhalten eine m x n-Binärmatrix.

Sie können eine beliebige Anzahl von Spalten in der Matrix auswählen und jede Zelle in dieser Spalte umdrehen (d. h. den Wert der Zelle von 0 auf 1 ändern oder umgekehrt).

Gib die maximale Anzahl von Zeilen zurück, deren Werte nach einer bestimmten Anzahl von Flips alle gleich sind.

Beispiel 1:

• Eingabe:Matrix = [[0,1],[1,1]]
• Ausgabe: 1
• Erklärung:Nachdem keine Werte umgedreht wurden, sind in einer Zeile alle Werte gleich.

Beispiel 2:

• Eingabe: Matrix = [[0,1],[1,0]]
• Ausgabe: 2
• Erklärung:Nach dem Umdrehen der Werte in der ersten Spalte haben beide Zeilen gleiche Werte.

Beispiel 3:

• Eingabe: Matrix = [[0,0,0],[0,0,1],[1,1,0]]
• Ausgabe: 2
• Erklärung:Nach dem Vertauschen der Werte in den ersten beiden Spalten haben die letzten beiden Zeilen gleiche Werte.

Einschränkungen:

• m == Matrix.Länge
• n == Matrix[i].length
• 1 <= m, n <= 300
• Matrix[i][j] ist entweder 0 oder 1.

Hinweis:

1. Das Umdrehen einer Teilmenge von Spalten ist so, als würde man jede Zeile bitweise mit einer Zahl K verknüpfen. Wir wollen Zeilen X mit X ^ K = alle Nullen oder alle Einsen. Dies ist dasselbe wie X = X^K ^K = (alle Nullen oder alle Einsen) ^ K, daher möchten wir Zeilen zählen, in denen entgegengesetzte Bits gesetzt sind. Wenn zum Beispiel K = 1, dann zählen wir die Zeilen X = (00000...001 oder 1111...110).

Lösung:

Wir können eine Hash-Map verwenden, um Zeilen zu gruppieren, die durch Umdrehen bestimmter Spalten identisch gemacht werden können. Zeilen, die identisch gemacht werden können, haben entweder das gleiche Muster oder ein komplementäres Muster (bitweise Negation).

Hier ist die Schritt-für-Schritt-Lösung:

Algorithmus:

1. Berechnen Sie für jede Zeile ihr Muster und ihr Komplementärmuster:
   • Das Muster ist die Reihe, wie sie ist.
   • Das Komplementärmuster ist das Ergebnis des Umdrehens aller Bits in der Zeile.
2. Verwenden Sie eine Hash-Map, um das Vorkommen von Mustern und deren Komplemente zu zählen.
3. Die maximale Anzahl für ein einzelnes Muster oder seine Ergänzung ergibt das Ergebnis.

Lassen Sie uns diese Lösung in PHP implementieren: 1072. Spalten umdrehen, um die maximale Anzahl gleicher Zeilen zu erreichen

  
  
  Erläuterung:




Muster und Ergänzung:


Für jede Zeile ist das Muster die verkettete Zeile (z. B. 010).
Das Komplement dreht alle Bits der Zeile um (z. B. 101).



Hash-Map: Zählen Sie das Vorkommen jedes Musters und seines Komplements. Dies hilft beim Gruppieren von Zeilen, die identisch gemacht werden können.

Max. Anzahl: Ermitteln Sie die maximale Anzahl eines einzelnen Musters oder seines Komplements, um zu bestimmen, wie viele Zeilen identisch gemacht werden können.



  
  
  Komplexität:




Zeitkomplexität: O(m x n), wobei m die Anzahl der Zeilen ist und n ist die Anzahl der Spalten.

Raumkomplexität: O(m x n), zum Speichern von Mustern in der Hash-Map.


Diese Lösung hält sich an die Einschränkungen und ist effizient für die Problemgröße.

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 vonSpalten umdrehen, um die maximale Anzahl gleicher Zeilen zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!