Zählen Sie quadratische Untermatrizen mit allen Einsen

1277. Zählen Sie quadratische Submatrizen mit allen Einsen

Schwierigkeit:Mittel

Themen:Array, Dynamische Programmierung, Matrix

Gib bei einer gegebenen m * n-Matrix aus Einsen und Nullen zurück, wie viele quadratische Untermatrizen alle Einsen haben.

Beispiel 1:

• Eingabe: Matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
• Ausgabe: 15
• Erklärung:
  • Es gibt 10 Quadrate der Seite 1.
  • Es gibt 4 Quadrate der Seite 2.
  • Es gibt 1 Quadrat der Seite 3.
  • Gesamtzahl der Quadrate = 10 4 1 = 15.

Beispiel 2:

• Eingabe: Matrix = [[1,0,1], [1,1,0], [1,1,0]]
• Ausgabe: 7
• Erklärung:
  • Es gibt 6 Quadrate der Seite 1.
  • Es gibt 1 Quadrat der Seite 2.
  • Gesamtzahl der Quadrate = 6 1 = 7.

Einschränkungen:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Hinweis:

1. Erstellen Sie eine Additivtabelle, die die Summe der Elemente der Submatrix mit der oberen Ecke bei (0,0) zählt.
2. Schleifen Sie alle Unterquadrate in O(n³) durch und prüfen Sie, ob die Summe das gesamte Array zu Einsen macht. Wenn dies überprüft wird, addieren Sie 1 zur Antwort.

Lösung:

Wir können Dynamische Programmierung (DP) verwenden, um die Anzahl der quadratischen Untermatrizen mit allen Einsen zu verfolgen, die an jeder Zelle in der Matrix enden können. Hier ist der Ansatz, um dies zu erreichen:

1. DP-Matrix-Definition:

   • Definieren Sie eine DP-Matrix dp, wobei dp[i][j] die Größe der größten quadratischen Untermatrix mit allen Einsen darstellt, deren rechte untere Ecke sich in Zelle (i, j) befindet.

2. Übergangsformel:

   • Für jede Zelle (i, j) in der Matrix:

     • Wenn Matrix[i][j] 1 ist, hängt der Wert von dp[i][j] vom Minimum der Quadrate ab, die durch Erweiterung von (i-1, j), (i, j) gebildet werden können -1) und (i-1, j-1). Die Übergangsformel lautet:

     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     

  - If `matrix[i][j]` is 0, `dp[i][j]` will be 0 because a square of ones cannot end at a cell with a zero.

1. Alle Quadrate zählen:

   • Akkumulieren Sie die Werte von dp[i][j] für alle (i, j), um die Gesamtzahl der Quadrate aller Größen zu erhalten.

2. Zeitkomplexität:

   • Die Lösung funktioniert in O(m > sind die Dimensionen der Matrix. Lassen Sie uns diese Lösung in PHP implementieren: 1277. Zählen Sie quadratische Submatrizen mit allen Einsen
   Erläuterung:

Wir initialisieren ein 2D-Array dp, um die Größe der größten quadratischen Submatrix zu verfolgen, die an jeder Position (i, j) endet. Für jede Zelle in der Matrix:

Wenn die Zelle eine 1 hat, berechnen wir dp[i][j] basierend auf benachbarten Zellen und addieren seinen Wert zu totalSquares.

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Abschließend enthält totalSquares die Anzahl aller quadratischen Untermatrizen mit allen Einsen.
2. Diese Lösung ist effizient und erfüllt die im Problem angegebenen Einschränkungen.
   • Kontaktlinks
3. 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 quadratische Untermatrizen mit allen Einsen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!