Zählen Sie quadratische Untermatrizen mit allen Einsen

Patricia Arquette
Freigeben: 2024-10-30 17:51:31
Original
294 Leute haben es durchsucht

Count Square Submatrices with All Ones

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(n3) 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
      
      Nach dem Login kopieren
      Nach dem Login kopieren
  - 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.
Nach dem Login kopieren
  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
Nach dem Login kopieren
Nach dem Login kopieren

    Abschließend enthält totalSquares die Anzahl aller quadratischen Untermatrizen mit allen Einsen.
  1. Diese Lösung ist effizient und erfüllt die im Problem angegebenen Einschränkungen.
    • Kontaktlinks
  2. Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem
  3. 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!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!