Condivisione della tecnologia

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. Combinazione

77. Combinazione

argomento

Dati due numeri interinEk, intervallo di ritorno[1, n]tutto possibile dentrokcombinazione di numeri.

puoi premerequalsiasi ordineRispondi.

Esempio 1:

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

Esempio 2:

输入：n = 1, k = 1
输出：[[1]]

suggerimento:

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

题解

Imposta un conteggio e calcola il numero di ciascuno. Quando count==k, inseriscilo nell'array. Questo è diverso dai precedenti, che erano permutazioni e combinazioni. È un po' come selezionare un array.

A partire da 1-n, imposta un array aggiuntivo per memorizzare i risultati di ogni volta. Il conteggio cambia dinamicamente Dopo aver assegnato i, il conteggio aumenta di uno e viene selezionato un numero da (i+1, n) in dfs. Conta... dopo aver effettuato il backtracing.

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. Ricerca unità

79. Ricerca di parole

argomento

dato unm x nGriglia di caratteri 2Dboarde una parola stringaword .Sewordesiste nella griglia, ritornatrue; Altrimenti, ritornafalse 。

Le parole devono essere formate da lettere in celle adiacenti in ordine alfabetico, dove le celle "adiacenti" sono quelle adiacenti orizzontalmente o verticalmente. Le lettere nella stessa cella non possono essere utilizzate ripetutamente.

Esempio 1:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

Esempio 2:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

Esempio 3:

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

suggerimento:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• boardEwordComposto solo da lettere inglesi maiuscole e minuscole

risposta

Routine simile.

Il metodo dfs + backtracking definisce innanzitutto una visita per contrassegnare se la posizione è stata contrassegnata durante ogni ricerca per evitare che la stessa posizione venga visitata più volte.

Per una posizione, è necessario effettuare una valutazione del confine per determinare se attraversa il confine. Quindi determinare se è stato visitato, se è stato trovato con successo e se la lettera nella posizione è diversa dalla lettera di destinazione.

dfs, cerca in giro.

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 Regina

51. Regina N

argomento

Secondo le regole degli scacchi, una regina può attaccare un pezzo sulla stessa riga o colonna o sulla stessa diagonale.

n Problema della reginaCiò che si studia è comencollocata la reginan×nsulla scacchiera e rendono le regine incapaci di attaccarsi a vicenda.

Dammi un numero interon, restituisce tutto diversoN problema della reginaLa sua soluzione.

Ogni soluzione ne contiene una diversan Problema della reginaIl piano di posizionamento dei pezzi degli scacchi, in questo piano'Q'E'.'Rappresentano rispettivamente la regina e il posto vuoto.

Esempio 1:

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

Esempio 2:

输入：n = 1
输出：[["Q"]]

suggerimento:

• 1 <= n <= 9

题意

N Queen richiede tre funzioni di etichettatura, una è la colonna, una è la diagonale principale e l'altra è la diagonale secondaria.

Poiché ci sarà sicuramente una regina posizionata in ogni riga, viene attraversata riga per riga. Quando l'ultima riga viene attraversata con successo e la regina viene posizionata con successo, è sufficiente. Quindi non è necessario impostare la funzione di marcatura delle righe.

A questo punto possiamo iniziare dalla prima riga e procedere per colonne. Determina se la colonna è falsa, se la diagonale principale è falsa e se la diagonale secondaria è falsa. In tal caso, vai alla colonna successiva. In caso contrario, imposta la posizione su Q, quindi esegui la stessa ricerca per la riga successiva. Metodo di backtracking, ricordarsi di ripristinare la posizione e le funzioni di marcatura dopo la ricerca.

Questo diagonale e subdiagonale. Può essere disegnato sulle coordinate, una è y=x+b, l'altra è y=-x+b.

Quindi b=yx, per rendere b>0, quindi aggiungiamo n. L'altro è 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;
        }
    }
};

Riassumere

Per il metodo del backtracking, trovare prima le condizioni al contorno e le condizioni finali. Generalmente, l'i impostato è uguale al numero di righe.

La condizione al contorno è generalmente quella di non oltrepassare il confine.

Generalmente è necessario impostare una funzione di marcatura. Quindi accedi riga per riga o posizione per posizione e la funzione del tag visitato sarà impostata su true. Quindi continua alla riga successiva o successiva (di solito in modo ricorsivo). Quindi ripristinare la funzione di marcatura di cui sopra e tabellone dopo aver terminato (di solito ne verrà impostato uno come risposta). Se corrisponde, push_back nell'array ans.