北京公司建一个网站需要多少钱_dw是什么软件_安徽seo团队_网络营销软件大全

N皇后

题目链接

题解

1. 画出决策树
2. 全局变量：ret用来统计结果，path统计每次的路径，checkcol检查行有没有Q，checkdig1检查主对角线有没有Q，checkdig2检查副对角线有没有Q
3. 剪枝：使用哈希表的策略，每一行不需要检查，每次都递归每一行该放的不会出现攻击，主对角线斜率一样，利用y-x = b，每一条线上截距是相同的，如果出现相同的就表明放过了Q，y-x可能为负数所以加上了n，副对角线y + x = b，和主对角线类似
4. 回溯：将列，主对角线和副对角线变为false，path[row][col]恢复为点
5. 递归出口：行越界的时候填完矩阵

代码

class Solution 
{
public:// 检查列,主对角线和副对角线// 行每次都只放一个不用检查,不会出现攻击bool checkcol[10],checkdig1[20],checkdig2[20];vector<vector<string>> ret;vector<string> path;int n;vector<vector<string>> solveNQueens(int _n) { n = _n;path.resize(n);for(int i = 0;i < n;i++){path[i].append(n,'.');}dfs(0);return ret;}void dfs(int row){if(n == row){ret.push_back(path);return;}for(int col = 0;col < n;col++)// 放置每一行{if(!checkcol[col] && !checkdig1[row + col] && !checkdig2[col-row+n]){path[row][col] = 'Q';checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = true;dfs(row+1);// 恢复现场checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = false;path[row][col] = '.';}}}
};

有效的数独

题目链接

题解

1. 算法原理：去遍历这个数独，如果遇到了数字就判断这个数字是否在这一行，这一列，这一个方格中，如果不在就标记为true，如果在就直接返回false，说明出现了第二次了
2. bool checkrow[i][nums]：用来检查这一行是否存在nums这个数
bool checkcol[j][nums]：用来检查这一列是否存在nums这个数
bool check[i/3][j/3][nums]：用来检查小方格中是否存在nums这个数，除3是把9 * 9的矩阵分为0，1，2下标的3*3的小方格，刚好第一个小方格中0，1，2下标的数除3都是0，第二，三个小方格也是如此

代码

class Solution 
{
public: bool checkrow[9][10];// 检查行bool checkcol[9][10];// 检查列bool check[3][3][10];// 检查小方格bool isValidSudoku(vector<vector<char>>& board) {for(int row = 0;row < 9;row++){for(int col = 0;col < 9;col++){if(board[row][col] != '.'){int nums = board[row][col] - '0';if(checkrow[row][nums] || checkcol[col][nums] || check[row/3][col/3][nums])return false;checkrow[row][nums] = checkcol[col][nums] = check[row/3][col/3][nums] = true;}}}return true;}
};

独解数

题目链接

题解

1. 画出决策树
2. 全局变量：checkcol检查列是否存在相同的数，checkrow检查行是否存在相同的数，gird检查小方格是否存在相同的数
3. 剪枝：bool dfs(board)，如果这一行最终有一个格子填不了了，就返回false，不往后填了，返回到上一层去填正确的数
4. 回溯：填了的数bool变为false，然后board恢复为点
5. 递归出口：函数走完填完所有的格子就结束了
6. 算法原理：这题主要考察三个返回，第一个返回，如果填完了dfs返回true了，就不需要填下一个i了，第二个返回，如果所有数都不满足，说明前面填错了，返回上一层重新填，第三个返回，如果所有有点的格子都填完了，并且没有错，就返回true

代码

class Solution 
{
public:bool checkrow[9][10];bool checkcol[9][10];bool gird[3][3][10];void solveSudoku(vector<vector<char>>& board) {for(int i = 0;i < 9;i++){for(int j = 0;j < 9;j++){if(board[i][j] != '.'){int nums = board[i][j] - '0';checkcol[j][nums] =  checkrow[i][nums] = gird[i/3][j/3][nums] = true;}}}dfs(board);}// 可以遍历所有空的位置的不需要row传参过来bool dfs(vector<vector<char>>& nums){for(int row = 0;row < 9;row++){for(int col = 0;col < 9;col++){if(nums[row][col] == '.'){for(char i = '1';i <= '9';i++){int data = i - '0';if(!checkcol[col][data] && !checkrow[row][data] && !gird[row/3][col/3][data]){nums[row][col] = i;checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = true;                       if(dfs(nums) == true) return true;// 如果这个位置填完了返回了true,就不要再试下一个i了// 恢复现场nums[row][col] = '.';checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = false;}}// 可能出现填不了的情况,1到9都不行return false;}}}// 空位置全都填完了,返回truereturn true;}
};

单词搜索

题目链接

题解

1. 画出决策树
2. 全局变量：m，n矩阵的大小，vis数组标记这个格子已经走过了
3. 剪枝：如果找不到第一个匹配的字符就剪枝
4. 回溯：如果找不到下一个匹配的字符就回溯
5. 递归出口：pos是字符串的长度，如果匹配到越界就说明找到了
6. 函数头：i，j是匹配到第一个字符的坐标，s是字符串，pos是匹配的字符的位置，board是矩阵
7. 利用向量找i，j的上下左右，就不需要用四个for循环了

代码

class Solution 
{
public:int m,n;// 标记该点是否使用过了bool vis[7][7];bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board,i,j,word,1)) return true;vis[i][j] = false;}}}// 都没找到匹配的字符串return false;}// 上下左右四个坐标int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size()) return true;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 && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;vis[x][y] = false;}}// 说明i,j位置找不到,是错误的位置return false;}
};

黄金矿工

题目链接

题解

1. 跟上一题非常类似，唯一要注意的是递归出口是可以每次更新的，因为写递归出口需要判断用for循环每次去更新比较麻烦
2. 可以使用path在参数中，dfs(path + gird[x][y])，这样每次加就不需要手动恢复现场了，函数会帮我们自动恢复现场，每次更新结果在dfs的开头，虽然多更新几次，但是不太麻烦
3. 我写的是全局的变量，需要恢复现场

代码

class Solution 
{
public:bool vis[16][16];int m,n;int ret = 0;int ans;int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] != 0){// 避免重复使用这个位置vis[i][j] = true;ans += grid[i][j];dfs(grid,i,j);ret = max(ans,ret);vis[i][j] = false;ans -= grid[i][j];}}}return ret;}int dx[4] = {0,0,-1,1};int dy[4] = {-1,1,0,0};void dfs(vector<vector<int>>& grid,int i,int j){for(int k = 0;k < 4;k++){int x = dx[k] + i,y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]!= 0){vis[x][y] = true;ans += grid[x][y];dfs(grid,x,y);ret = max(ans,ret);vis[x][y] = false;ans -= grid[x][y];}}}
};

不同路径

题目链接

题解

1. 这题要注意的一点是设计一个全局变量count，用来统计0的个数，在参数中多一个step，如果step和count相同，并且这个点的值是2，那么就是一个路径
2. 这题和上题也非常相似

代码

class Solution 
{
public:// 统计0的个数int count;bool vis[21][21];int m,n;int ans;int uniquePathsIII(vector<vector<int>>& grid) {// 初始化为局部变量了,符了m = grid.size(),n = grid[0].size();int dx,dy;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == 0) count++;else if(grid[i][j] == 1){dx = i;dy = j; }}}    grid[dx][dy] = true;dfs(grid,dx,dy,0);return ans;}int dx[4] = {0,0,-1,1};int dy[4] = {-1,1,0,0};void dfs(vector<vector<int>>& grid,int i,int j,int step){if(count == step && grid[i][j] == 2){ans++;return;}for(int k = 0;k < 4;k++){int x = dx[k] + i,y = dy[k] + j;if(x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 0){vis[x][y] = true;dfs(grid,x,y,step + 1);vis[x][y] = false;}if(count == step&&x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 2){vis[x][y] = true;dfs(grid,x,y,step);vis[x][y] = false;}}}
};

总结

1. 题目识别什么时候用矩阵搜索？
当出现向上，向下，向左，向右搜索时可以使用
2. 怎么使用矩阵搜索？
上面的三题里做了，就是模版
3. 如果是矩阵填空的题怎么做，例如N皇后？
可以用bool数组标记填过的行列斜对角线检查是否有效，然后一层一层去搜索，这种题主要也是画决策树，就是多了几个bool数组检查使用过的格子，之后不再使用这个格子