Likou-Backtracking-Methode

2024-07-12

Was ist Backtracking?

Wenn wir bei der Suche nach einem bestimmten Knoten feststellen, dass der aktuelle Knoten (und seine Unterknoten) nicht das erforderliche Ziel sind, greifen wir auf den ursprünglichen Knoten zurück, um die Suche fortzusetzen und den geänderten Zustand des aktuellen Knotens wiederherzustellen.

Denken Sie an zwei kleine Tipps:Die erste besteht darin, den Status per Referenz (&) zu übergeben, und die zweite darin, alle Statusänderungen nach Abschluss der Rekursion zu ändern.

Im Allgemeinen gibt es zwei Situationen für das Zurückverfolgen von Änderungen: Eine besteht darin, die letzte Ausgabe zu ändern, z. B. Permutation und Kombination, und die andere darin, das Zugriffsziel zu ändern.

Denken Sie beispielsweise an die Suche nach einer Zeichenfolge in einer Matrix.

46.Komplette Anordnung

46. Vollständige Anordnung

Thema
Gegeben sei ein Array ohne doppelte Zahlennums, gib es zurückalle möglichen Permutationen .du kannstIn irgendeiner ReihenfolgeAntwort zurückgeben.

Beispiel 1:
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Beispiel 2:
输入：nums = [0,1]
输出：[[0,1],[1,0]]
Beispiel 3:
输入：nums = [1]
输出：[[1]]
Hinweis:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
numsalle ganzen Zahlen invoneinander verschieden

Antwort

Um alle sortierten Kombinationen des Arrays auszugeben, können wir die Backtracking-Methode verwenden.

Bestimmen Sie zunächst eine Position und tauschen Sie diese dann mit jeder weiteren Position aus. Gehen Sie nach dem Wechsel zum nächsten Ort. Nachdem diese Reihe von Schritten abgeschlossen ist, müssen Sie die ersetzten ersetzen. Das ist die Backtracking-Methode.


class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        back(nums,0,ans);
        return ans;
    }
    void back(vector<int>& nums,int n,vector<vector<int>>& ans){
        int i;
        if(n==nums.size()-1)
            ans.push_back(nums);
        for(i=n;i<nums.size();i++){
            swap(nums[i],nums[n]);
            back(nums,n+1,ans);
            swap(nums[i],nums[n]);
        }
    }
};

77. Kombination

Thema

Gegeben sind zwei ganze ZahlennUndk, Rückgabebereich[1, n]alles möglich inkZahlenkombination.

Sie können drückenjede BestellungAntwort zurückgeben.

Beispiel 1:
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
Beispiel 2:
输入：n = 1, k = 1
输出：[[1]]
Hinweis:

1 <= n <= 20
1 <= k <= n

题解

Legen Sie eine Anzahl fest und berechnen Sie deren Anzahl. Wenn count==k, fügen Sie sie in das Array ein. Dies unterscheidet sich von den vorherigen, bei denen es sich um Permutationen und Kombinationen handelte. Dies ähnelt in etwa der Auswahl eines Arrays.

Richten Sie ausgehend von 1-n ein zusätzliches Array ein, um die Ergebnisse jeder Zeit zu speichern. Die Anzahl ändert sich dynamisch. Nach der Zuweisung von i erhöht sich die Anzahl um eins und eine Zahl wird aus (i+1, n) in dfs ausgewählt. Zählen – nach der Rückverfolgung.
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> c(k,0);
        int count;
        dfs(n,k,1,ans,c,count);
        return ans;
    }
    void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){
        int i;
 
        if(count==k){
            ans.push_back(c);
            return ;
        }
            
        for(i=level;i<=n;i++){
            c[count++]=i;
            dfs(n,k,i+1,ans,c,count);
            --count;
        }
    }
};

79. Einheitensuche

79. Wortsuche

Thema

angenommenm x n2D-Zeichenrasterboardund ein Zeichenfolgenwortword .Wennwordexistiert im Raster, kehrt zurücktrue; Ansonsten zurückfalse 。

Wörter müssen aus Buchstaben in benachbarten Zellen in alphabetischer Reihenfolge gebildet werden, wobei „benachbarte“ Zellen diejenigen sind, die horizontal oder vertikal benachbart sind. Buchstaben in derselben Zelle dürfen nicht wiederholt verwendet werden.

Beispiel 1:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
Beispiel 2:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
Beispiel 3:
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
Hinweis:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
boardUndwordBesteht nur aus englischen Groß- und Kleinbuchstaben

Antwort

Ähnliche Routine.

Die DFS + Backtracking-Methode definiert zunächst einen Besuch, um zu markieren, ob der Standort bei jeder Suche markiert wurde, um zu verhindern, dass derselbe Standort mehrmals besucht wird.

Für einen Standort muss eine Grenzbeurteilung vorgenommen werden, um festzustellen, ob er die Grenze überschreitet. Stellen Sie dann fest, ob es besucht wurde, ob es erfolgreich gefunden wurde und ob sich der Buchstabe an der Position vom Zielbuchstaben unterscheidet.

dfs, suche herum.


class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty())
            return false;
        int m=board.size(),n=board[0].size();
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        int i,j;
        bool find=false;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++)
                back(i,j,board,word,find,visit,0);
        }
        return find;
    }
    void back(int i,int j,vector<vector<char>>& board,string& word,
    bool& find,vector<vector<bool>>& visit,int level){
        if(i<0||i>=board.size()||j<0||j>=board[0].size())
            return ;
      
        if(visit[i][j]||find||board[i][j]!=word[level])
            return ;
        if(level==word.size()-1){
            find=true;
            return ;
        }
        visit[i][j]=true;
        back(i+1,j,board,word,find,visit,level+1);
        back(i-1,j,board,word,find,visit,level+1);
        back(i,j+1,board,word,find,visit,level+1);
        back(i,j-1,board,word,find,visit,level+1);
        visit[i][j]=false;
    }
};

51.N Königin

51. Königin N

Thema

Nach den Schachregeln kann eine Dame eine Figur in derselben Reihe oder Spalte oder auf derselben Diagonale angreifen.

n Queen-ProblemEs wird untersucht, wie es gehtnKönigin eingesetztn×nauf dem Schachbrett und verhindern, dass die Damen sich gegenseitig angreifen können.

Geben Sie eine ganze Zahl ann, gibt alles anders zurückN Königinproblems Lösung.

Jede Lösung enthält eine anderen Queen-ProblemDer Plan zur Platzierung der Schachfiguren in diesem Plan'Q'Und'.'Sie repräsentieren jeweils die Königin und den freien Platz.

Beispiel 1:
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
Beispiel 2:
输入：n = 1
输出：[["Q"]]
Hinweis:

1 <= n <= 9

题意

N Queen erfordert drei Beschriftungsfunktionen: eine ist die Spalte, eine ist die Hauptdiagonale und die andere ist die Nebendiagonale.

Da in jeder Reihe auf jeden Fall eine Königin platziert wird, wird diese Reihe für Reihe durchquert. Wenn die letzte Reihe erfolgreich durchquert und die Königin erfolgreich platziert wurde, reicht es aus. Daher ist es nicht erforderlich, die Zeilenmarkierungsfunktion einzustellen.

Zu diesem Zeitpunkt können wir mit der ersten Zeile beginnen und spaltenweise durchlaufen. Bestimmen Sie, ob die Spalte falsch ist, ob die Hauptdiagonale falsch ist und ob die Nebendiagonale falsch ist. Wenn ja, gehen Sie zur nächsten Spalte. Wenn nicht, setzen Sie die Position auf Q und führen Sie dann die gleiche Suche für die nächste Zeile durch. Denken Sie bei der Backtracking-Methode daran, die Positions- und Markierungsfunktionen nach der Suche wiederherzustellen.

Diese Diagonale und Subdiagonale. Es kann anhand der Koordinaten gezeichnet werden, eines ist y=x+b, das andere ist y=-x+b.

Also b=yx, um b>0 zu machen, also addieren wir n. Das andere ist y+x.
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        if(n==0)
            return {};
        vector<string> board(n,string(n,'.'));
        vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);
        back(n,ans,board,c,l,r,0);
        return ans;
    }
    void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,
    vector<bool>& l,vector<bool>& r,int row){
        if(row==n){
            ans.push_back(board);
            return ;
        }
        int i;
        for(i=0;i<n;i++){
            if(c[i]||l[row-i+n]||r[row+i]){
                continue;
            }
            board[row][i]='Q';
            c[i]=l[row-i+n]=r[row+i]=true;
            back(n,ans,board,c,l,r,row+1);
            board[row][i]='.';
            c[i]=l[row-i+n]=r[row+i]=false;
        }
    }
};

Zusammenfassen

Für die Backtracking-Methode müssen zunächst die Randbedingungen und die Endbedingungen ermittelt werden. Im Allgemeinen ist der i-Satz gleich der Anzahl der Zeilen.

Die Randbedingung besteht im Allgemeinen darin, die Grenze nicht zu überschreiten.

Im Allgemeinen muss eine Markierungsfunktion eingestellt werden. Greifen Sie dann Zeile für Zeile oder Position für Position zu, und die besuchte Tag-Funktion wird auf „true“ gesetzt. Fahren Sie dann mit der nächsten oder nächsten Zeile fort (normalerweise rekursiv). Stellen Sie dann nach Abschluss die obige Markierungsfunktion wieder her und ordnen Sie sie an (normalerweise wird eine als Antwort festgelegt). Wenn es übereinstimmt, push_back zum ans-Array.

Technologieaustausch