本文主要是介绍代码随想录算法训练营第二十六天|leetcode37、51题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、leetcode第51题
本题将递归与回溯结合，重点在于如何判断该位置能否放置皇后，也就是该位置同一行、同一列、45度对角线和135度对角线是否已经放置了皇后，如果已经放置皇后则该位置不合法。因此，需要在每一行的每一列都试探性地插入皇后，如果合法则进行下一行的皇后插入，否则回溯倒退将皇后插入下一列。
具体代码如下：
class Solution {
public:vector<vector<string>>result;vector<vector<string>> solveNQueens(int n) {vector<string>s(n,string(n,'.'));backtracking(n,0,s);return result;}void backtracking(int n,int row,vector<string>&s){if(row==n){result.push_back(s);return;}for(int col=0;col<n;col++){if(isvalid(row,col,s,n)){s[row][col]='Q';backtracking(n,row+1,s);s[row][col]='.';}}}bool isvalid(int row,int col,vector<string>&s,int n){for(int i=0;i<row;i++){if(s[i][col]=='Q'){return false;}}for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){if(s[i][j]=='Q'){return false;}}for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){if(s[i][j]=='Q'){return false;}}return true;}
};二、leetcode第37题
本题比上一题要求要更为复杂，需要在每个位置都插入数字，因此需要进行双层回溯，对数独的每一个空位置都进行判断是否合法，如果合法则添加数字并继续探索下一个位置，如果不合法则需要回溯。
具体代码如下：
class Solution {
public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}bool backtracking(vector<vector<char>>& board){for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]=='.'){for(char k='1';k<='9';k++){if(isvalid(i,j,board,k)){board[i][j]=k;if(backtracking(board)){return true;}board[i][j]='.';}}return false;}}}return true;}bool isvalid(int i,int j,vector<vector<char>>& board,char k){for(int a=0;a<9;a++){if(board[i][a]==k){return false;}}for(int b=0;b<9;b++){if(board[b][j]==k){return false;}}int starti=(i/3)*3;int startj=(j/3)*3;for(int i=starti;i<starti+3;i++){for(int j=startj;j<startj+3;j++){if(board[i][j]==k){return false;}}}return true;}
};这篇关于代码随想录算法训练营第二十六天|leetcode37、51题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
