Finden Sie einen effizienten Weg

Hallo Leute! Heute habe ich drei Probleme mit LeetCode gelöst: Unique Paths, Spiral Matrix und N-Queens. Lassen Sie uns diese Probleme durchgehen.

Problem mit eindeutigen Pfaden

Wir erhalten zwei Zahlen, die die Anzahl der Zeilen und die Anzahl der Spalten darstellen. Unsere Aufgabe besteht darin, die Gesamtzahl der eindeutigen Pfade zu ermitteln, um die Position (m-1,n-1) von (0,0) aus zu erreichen. Um dieses Problem zu lösen, können wir einen rekursiven Ansatz verfolgen. Wir können bei (0,0) beginnen und rekursiv Schritte finden, um nach rechts und unten zu gelangen, bis wir die erforderliche Position erreichen. Um insgesamt eindeutige Pfade zu finden, würden wir die richtigen Schritte zu den unteren Schritten hinzufügen und sie zurückgeben. Allerdings gibt es bei diesem Ansatz ein kleines Problem: Die Lösungen können sich mehrmals wiederholen. Um dies zu überwinden, besteht der alternative Ansatz darin, eine DP-Matrix zu verwenden. Wir erstellen eine DP-Matrix mit der gleichen Anzahl von Zeilen und Spalten wie die Eingabe und initialisieren alle Positionen der DP-Matrix mit 1. Schließlich geben wir den Wert in der Lats-Zelle der DP-Matrix als Gesamtzahl eindeutiger Pfade zurück.

Spiralmatrix

Wir erhalten eine Matrix und müssen eine Liste zurückgeben, die die Elemente der Matrix in spiralförmiger Reihenfolge enthält. Um dieses Problem zu lösen, können wir Indizierungsgrenzen als Bedingungen für die Ausführung einer Schleife verwenden. Wir durchlaufen die Matrix von links nach rechts und können eine for-Schleife verwenden. Dann bewegen wir uns mit einer weiteren Schleife von der oberen rechten Ecke zur unteren rechten Ecke. Mit einer dritten Schleife gehen wir von der unteren rechten Ecke zur unteren linken Ecke. Schließlich bewegen wir uns mit einer vierten Schleife von der unteren linken Ecke zur oberen linken Ecke. Auf diese Weise verwenden wir vier verschiedene Schleifen zum Durchlaufen in alle vier Richtungen und steuern sie mit Indexierungsgrenzen.

N-Queens

Uns wird eine Eingabezahl n gegeben, wir müssen die Anzahl der Möglichkeiten finden, n Königinnen in einer nxn-Matrix so zu platzieren, dass sich keine zwei Königinnen gegenseitig angreifen. Das bedeutet, dass sich keine zwei Damen in derselben Reihe, Spalte oder Diagonale befinden sollten. Um dieses Problem zu lösen, können wir Rekursions- und Backtracking-Konzepte verwenden. Wir können zunächst eine Rekursion durchführen, um den Vorgang mehrmals zu wiederholen. denn wir müssen alle möglichen Möglichkeiten finden, Königinnen zu platzieren. Wenn wir nicht die richtige Position zum Platzieren der Königin gefunden haben, wird ein Zurückverfolgen durchgeführt. Dann können wir „Q“ durch „.“ ersetzen und den Vorgang für die nächste Position wiederholen.

Wir können die obige Lösung optimieren, indem wir drei Listen verwenden. Eine Liste besteht darin, die Anzahl der Zeilen im Auge zu behalten. Nehmen wir an, wir haben n Zeilen. Wir werden n Nullen in die Liste einfügen und die jeweilige Null durch eine ersetzen, wenn diese bestimmte Zeile eine Königin hat. Dadurch wird unnötiges Zurückverfolgen vermieden. Ebenso gilt die zweite Liste für die untere Diagonale und die dritte Liste für die obere Diagonale. Beide Diagonallisten enthalten 2n-1 Elemente, die alle zunächst auf Null gesetzt sind. Während wir die Matrix durchlaufen, um Königinnen zu platzieren, aktualisieren wir die entsprechende Zeilen- oder Diagonalliste, indem wir 0 durch 1 ersetzen, wenn die Königin platziert wird. Dies zeigt an, dass in der entsprechenden Diagonale oder Reihe keine Damen mehr platziert werden können. Auf diese Weise funktioniert dieser Ansatz effizient.

Ich hoffe, dass meine Erfahrung hilfreich sein wird.

Das obige ist der detaillierte Inhalt vonFinden Sie einen effizienten Weg. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!