在线做网页的网站,西安网站制作顶尖,平台搭建,语文建设编辑部官方网站目录
编辑 一#xff0c;N皇后问题
1.题意
2.解释
3.题目接口
4.解题思路及代码
二#xff0c;单词搜索
1.题意
2.解释
3.题目接口
4.思路及代码 一#xff0c;N皇后问题
1.题意 按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上…
目录
编辑 一N皇后问题
1.题意
2.解释
3.题目接口
4.解题思路及代码
二单词搜索
1.题意
2.解释
3.题目接口
4.思路及代码 一N皇后问题
1.题意 按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 2.解释 这道题其实就是在下国际象棋。国际象棋的皇后是可以走上下左右和斜对角六个方向的。所以在放置皇后时我们就要考虑一下在那个位置放入一个皇后我们才不会被攻击。直到将所有能防止皇后的位置放好以后便返回放好皇后以后的棋盘。 3.题目接口
class Solution {
public:vectorvectorstring solveNQueens(int n) {}
};
4.解题思路及代码 class Solution {
public:vectorvectorstringret;//存结果vectorstringboard;//开棋盘bool rowCheak[10];bool colCheak[10];bool digit1[20];bool digit2[20];//因为对于一条对角线有row colb-row-col b。但是b在[-n,n]。//为了将负数下标去掉所以在左右两边都加上n:row-coln bn-[0,2*n]//所以diagonal要开20个空间int n;vectorvectorstring solveNQueens(int _n) {n _n;board.resize(n);for(int i 0;in;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;coln;col){if(board[row][col].!rowCheak[row]!colCheak[col]!digit1[row-coln]!digit2[rowcol]){board[row][col] Q;rowCheak[row]colCheak[col]digit1[row-coln] digit2[rowcol] true;dfs(row1);board[row][col] .;rowCheak[row]colCheak[col]digit1[row-coln] digit2[rowcol] 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(vectorvectorchar board, string word) {}
};
4.思路及代码 1.第一种解法 class Solution {
public:vectorvectorboolused;int m,n;bool exist(vectorvectorchar board, string word) {m board.size();n board[0].size();used.resize(m);for(int i 0;im;i){used[i].resize(n);}for(int i 0;im;i){for(int j 0;jn;j){ if(dfs(board,i,j,word,0)) return true;//df函数只有在将word的全部字母找到以后才能返回true。}}return false;//全部遍历完了还没有结果便返回false} bool dfs(vectorvectorchar board,int i,int j,string word,int pos){if(i0||im||j0||jn||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,pos1)||dfs(board,i,j1,word,pos1)||dfs(board,i-1,j,word,pos1)||dfs(board,i1,j,word,pos1);//在这个位置的上下左右寻找used[i][j] false;//res可能是false所以要恢复现场调整上一层的寻找的下标return res;}
}; 2.第二种解法 class Solution {
public:vectorvectorboolused;int m,n;bool exist(vectorvectorchar board, string word) {m board.size();n board[0].size();used.resize(m);for(int i 0;im;i){used[i].resize(n);}for(int i 0;im;i){for(int j 0;jn;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(vectorvectorchar 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;k4;k){int x idx[k],y jdy[k];if(x0xmy0ynboard[x][y] word[pos]!used[x][y])//只统计对的情况{used[x][y] true;if(dfs(board,x,y,word,pos1)) return true;used[x][y] false;}}return false;}
};
