技術共有

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. コンビネーション

トピック

2 つの整数が与えられた場合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

题解

countを設定し、count==kのときのそれぞれの数を計算し、配列に入れます。これは、順列と組み合わせであった以前のものとは異なります。これは配列の選択に少し似ています。

1 ～ n から開始して、各時間の結果を保存する追加の配列を設定します。 i を割り当てた後、count は動的に変化し、dfs の (i+1, n) から数値が選択されます。バックトレース後、カウントします。

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 n2D キャラクターグリッド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大文字と小文字の英字のみで構成されています

答え

同様のルーチン。

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.N クイーン

51. クイーンN

トピック

チェスのルールによれば、クイーンは同じ行または列、または同じ対角線上にある駒を攻撃できます。

クイーン問題研究されているのは、どのようにするかということですnに置かれた女王n×nチェス盤上でクイーン同士を攻撃できなくなります。

整数を与えてくださいn、すべて異なるものを返しますん 女王問題の解決策。

各ソリューションには異なるものが含まれていますクイーン問題この計画におけるチェスの駒の配置計画'Q'そして'.'それぞれ女王と空席を表しています。

例 1:

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

例 2:

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

ヒント：

• 1 <= n <= 9

题意

N Queen には 3 つのラベル付け関数が必要です。1 つは列、1 つは主対角、もう 1 つは副対角です。

各行には必ずクイーンが配置されるため、行ごとに走査され、最後の行が正常に走査され、クイーンが正常に配置されれば十分です。したがって、行マーキング機能を設定する必要はありません。

現時点では、最初の行から開始して列ごとに移動できます。列が false かどうか、主対角線が false かどうか、および 2 次対角線が false かどうかを判断します。存在する場合は、次の列に移動します。そうでない場合は、位置を Q に設定し、次の行に対して同じ検索を実行します。バックトラッキング方法では、検索後に位置とマーキング機能を忘れずに復元してください。

この対角線と副対角線。座標上に描画できます。1 つは y=x+b、もう 1 つは y=-x+b です。

したがって、b=yx となり、b>0 となるため、n を追加します。もう 1 つは 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;
        }
    }
};

要約する

バックトラッキング方法では、まず境界条件と終了条件を求めます。一般に、i セットは行数と同じです。

境界条件は通常、境界を越えないことです。

通常はマーキング機能の設定が必要です。次に、行ごとまたは位置ごとにアクセスし、訪問済みタグ関数が true に設定されます。次に、次の行または次の行に進みます (通常は再帰的に)。その後、終了後に上記のマーク機能とボードを復元します (通常は 1 つが答えとして設定されます)。一致する場合は、ans 配列にプッシュバックされます。