Κοινή χρήση τεχνολογίας

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. Συνδυασμός

77. Συνδυασμός

θέμα

Δίνονται δύο ακέραιοι αριθμοίnκαιk, εύρος επιστροφής[1, n]όλα δυνατά σεkσυνδυασμό αριθμών.

μπορείτε να πατήσετεοποιαδήποτε παραγγελίαΕπιστροφή απάντηση.

Παράδειγμα 1:

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

Παράδειγμα 2:

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

ίχνος:

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

题解

Ορίστε έναν αριθμό και υπολογίστε τον αριθμό του καθενός. Αυτό είναι διαφορετικό από τα προηγούμενα, που ήταν μεταθέσεις και συνδυασμοί. Αυτό μοιάζει λίγο με την επιλογή ενός πίνακα.

Ξεκινώντας από το 1-n, ρυθμίστε έναν επιπλέον πίνακα για να αποθηκεύσετε τα αποτελέσματα κάθε φορά. Η μέτρηση αλλάζει δυναμικά Μετά την εκχώρηση i, η μέτρηση αυξάνεται κατά ένα και επιλέγεται ένας αριθμός από (i+1, n) σε dfs. Μέτρηση-- μετά την αναδρομή.

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. Αναζήτηση μονάδας

79. Αναζήτηση λέξεων

θέμα

δίνεται αm x nΔισδιάστατο πλέγμα χαρακτήρωνboardκαι μια λέξη χορδήword .ανwordυπάρχει στο πλέγμα, επιστρέφειtrueΔιαφορετικά, επιστρέψτεfalse 。

Οι λέξεις πρέπει να σχηματίζονται από γράμματα σε γειτονικά κελιά με αλφαβητική σειρά, όπου "γειτονικά" κελιά είναι εκείνα που είναι γειτονικά οριζόντια ή κάθετα. Τα γράμματα στο ίδιο κελί δεν επιτρέπεται να χρησιμοποιούνται επανειλημμένα.

Παράδειγμα 1:

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

Παράδειγμα 2:

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

Παράδειγμα 3:

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

ίχνος:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• boardκαιwordΑποτελείται μόνο από κεφαλαία και πεζά αγγλικά γράμματα

απάντηση

Παρόμοια ρουτίνα.

Η μέθοδος backtracking dfs + ορίζει πρώτα μια επίσκεψη για να επισημάνει εάν η τοποθεσία έχει επισημανθεί κατά τη διάρκεια κάθε αναζήτησης για να αποτρέψει την επανειλημμένη επίσκεψη της ίδιας τοποθεσίας.

Για μια τοποθεσία, πρέπει να γίνει μια οριακή κρίση για να καθοριστεί εάν διασχίζει το όριο. Στη συνέχεια, καθορίστε εάν έχει επισκεφθεί, εάν βρέθηκε με επιτυχία και εάν το γράμμα στη θέση είναι διαφορετικό από το γράμμα-στόχο.

dfs, ψάξε τριγύρω.

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.Ν Βασίλισσα

51. Βασίλισσα Ν

θέμα

Σύμφωνα με τους κανόνες του σκακιού, μια βασίλισσα μπορεί να επιτεθεί σε ένα κομμάτι στην ίδια σειρά ή στήλη ή στην ίδια διαγώνιο.

n Πρόβλημα βασίλισσαςΑυτό που μελετάται είναι πώς ναnβασίλισσα τοποθετείται μέσαn×nστη σκακιέρα, και κάνουν τις βασίλισσες να μην μπορούν να επιτεθούν η μία στην άλλη.

Σας δίνουμε έναν ακέραιοn, επιστρέφει όλα διαφορετικάn πρόβλημα βασίλισσαςs λύση.

Κάθε λύση περιέχει διαφορετικήn Πρόβλημα βασίλισσαςΤο σχέδιο τοποθέτησης σκακιού, σε αυτό το σχέδιο'Q'και'.'Αντιπροσωπεύουν τη βασίλισσα και την άδεια έδρα αντίστοιχα.

Παράδειγμα 1:

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

Παράδειγμα 2:

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

ίχνος:

• 1 <= n <= 9

题意

Το N Queen απαιτεί τρεις συναρτήσεις σήμανσης, μία είναι η στήλη, μία είναι η κύρια διαγώνιος και η άλλη είναι η δευτερεύουσα διαγώνιος.

Επειδή σίγουρα θα τοποθετηθεί μια βασίλισσα σε κάθε σειρά, διασχίζεται σειρά με σειρά Όταν η τελευταία σειρά διανυθεί με επιτυχία και η βασίλισσα τοποθετηθεί με επιτυχία, είναι αρκετό. Επομένως, δεν χρειάζεται να ρυθμίσετε τη λειτουργία σήμανσης σειρών.

Αυτή τη στιγμή μπορούμε να ξεκινήσουμε από την πρώτη σειρά και να διασχίσουμε στήλες. Προσδιορίστε εάν η στήλη είναι ψευδής, εάν η κύρια διαγώνιος είναι ψευδής και εάν η δευτερεύουσα διαγώνιος είναι ψευδής. Εάν ναι, μεταβείτε στην επόμενη στήλη Εάν όχι, ορίστε τη θέση σε Q και, στη συνέχεια, εκτελέστε την ίδια αναζήτηση για την επόμενη σειρά. Μέθοδος backtracking, θυμηθείτε να επαναφέρετε τις λειτουργίες θέσης και σήμανσης μετά την αναζήτηση.

Αυτή η διαγώνιος και υποδιαγώνιος. Μπορεί να σχεδιαστεί στις συντεταγμένες, η μία είναι y=x+b, η άλλη είναι y=-x+b.

Άρα b=yx, για να κάνουμε b>0, οπότε προσθέτουμε n. Το άλλο είναι 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;
        }
    }
};

Συνοψίζω

Για τη μέθοδο backtracking, βρείτε πρώτα τις οριακές συνθήκες και τις συνθήκες λήξης. Γενικά, το σύνολο i είναι ίσο με τον αριθμό των σειρών.

Η οριακή συνθήκη είναι γενικά να μην υπερβείτε το όριο.

Γενικά, πρέπει να οριστεί μια λειτουργία σήμανσης. Στη συνέχεια, αποκτήστε πρόσβαση γραμμή προς γραμμή ή θέση προς θέση και η συνάρτηση ετικέτας επίσκεψης ορίζεται σε true. Στη συνέχεια, συνεχίστε στην επόμενη ή επόμενη γραμμή (συνήθως αναδρομικά). Στη συνέχεια, επαναφέρετε την παραπάνω λειτουργία σήμανσης και την πλακέτα μετά την ολοκλήρωση (συνήθως ορίζεται μία ως απάντηση). Εάν ταιριάζει, push_back στον πίνακα ans.