递归算法学习——N皇后问题，单词搜索

目录

​编辑

一，N皇后问题

1.题意

2.解释

3.题目接口

4.解题思路及代码

二，单词搜索

1.题意

2.解释

3.题目接口

4.思路及代码

---

一，N皇后问题

1.题意

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

2.解释

这道题其实就是在下国际象棋。国际象棋的皇后是可以走上下左右和斜对角六个方向的。所以在放置皇后时我们就要考虑一下在那个位置放入一个皇后我们才不会被攻击。直到将所有能防止皇后的位置放好以后便返回放好皇后以后的棋盘。

3.题目接口

class Solution {
public:vector<vector<string>> solveNQueens(int n) {}
};

4.解题思路及代码

class Solution {
public:vector<vector<string>>ret;//存结果vector<string>board;//开棋盘bool rowCheak[10];bool colCheak[10];bool digit1[20];bool digit2[20];//因为对于一条对角线有row = col+b->row-col = b。但是b在[-n,n]。//为了将负数下标去掉所以在左右两边都加上n:row-col+n = b+n->[0,2*n]//所以diagonal要开20个空间int n;vector<vector<string>> solveNQueens(int _n) {n = _n;board.resize(n);for(int i = 0;i<n;i++){board[i].append(n,'.');}dfs(0);return ret;} void dfs(int row){if(row == n){ret.push_back(board);return;}for(int col = 0;col<n;col++){if(board[row][col]=='.'&&!rowCheak[row]&&!colCheak[col]&&!digit1[row-col+n]&&!digit2[row+col]){board[row][col] = 'Q';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = true;dfs(row+1);board[row][col] = '.';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = false;}}}
};

对于这道题，采用的便是类似于哈希表的解决方法。

1.首先我们得找四个布尔类型的数组：rowCheak,colCheak,digit1,digit2。这四个布尔类型的数组分别标记的是行，列，左对角线，右对角线。

2.然后便是递归的设计了，我们可以采用一个一个的试的方法，但是这样效率太低了。所以我们便采用一行一行试的方法来设计递归函数。

 dfs(0);

首先从第0行开始。每次遍历一行，每次在dfs函数里面遍历每一行的每一列。当对应行列下标的位置不是'Q'并且这一个格子的行，列，对角线都没有被使用过便可以插入Q。然后再遍历下一行，假设这一行填下的皇后会导致得不到结果便要回溯处理。

3.当row越界的时候说明我们的皇后已经填完了，在这个时候便可以返回了。

二，单词搜索

1.题意

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

2.解释

这一道题让我们做的便是在给定一个m*n大小的棋盘并且给定一个单词word的情况下让我们去在这个棋盘里面找到这个单词的每一个字母。并且这个单词的每一个相邻字母在棋盘中还是相邻的。

3.题目接口

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {}
};

4.思路及代码

1.第一种解法：

class Solution {
public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){     if(dfs(board,i,j,word,0)) return true;//df函数只有在将word的全部字母找到以后才能返回true。}}return false;//全部遍历完了还没有结果便返回false} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(i<0||i>=m||j<0||j>=n||used[i][j]||board[i][j]!=word[pos]) //答案不对的情况{return false;}if(pos == word.size()-1)//当最后一个字母也被匹配到了便可以返回true{return true;}used[i][j] = true;//使用过了便标记一下bool res = dfs(board,i,j-1,word,pos+1)||dfs(board,i,j+1,word,pos+1)||dfs(board,i-1,j,word,pos+1)||dfs(board,i+1,j,word,pos+1);//在这个位置的上下左右寻找used[i][j] = false;//res可能是false所以要恢复现场调整上一层的寻找的下标return res;}
};

2.第二种解法

class Solution {
public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){     if(board[i][j] == word[0]){used[i][j] =true;if(dfs(board,i,j,word,1)) return true;used[i][j] = false;}}}return false;} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size()){return true;}int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};//用数组和for循环来表示上下左右寻找for(int k =0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] ==word[pos]&&!used[x][y])//只统计对的情况{used[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;used[x][y] = false;}}return false;}
};