332.重新安排行程
class Solution {
public:
vector<string> result;
bool backtracking(vector<vector<string>>& tickets, vector<bool>& used){
if(result.size()==tickets.size()+1){
return true;
}
for(int i=0; i<tickets.size(); i++){
if(used[i] == true){
continue;
}
if(tickets[i][0]==result.back()){
result.push_back(tickets[i][1]);
used[i] = true;
if(backtracking(tickets, used)) return true;
result.pop_back();
used[i] = false;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
result.push_back("JFK");
vector<bool> used(tickets.size(), false);
backtracking(tickets, used);
return result;
}
};
参考文章:代码随想录-332.重新安排行程
51. N皇后
class Solution {
public:
vector<vector<string>> result;
bool isValid(int col, int row, vector<string>& temp, int n){
for(int i=0; i<row; i++){
if(temp[i][col]=='Q') return false;
}
for(int i=row-1, j=col-1; i>=0&&j>=0; i--, j--){
if(temp[i][j]=='Q') return false;
}
for(int i=row-1, j=col+1; i>=0&&j<n; i--, j++){
if(temp[i][j]=='Q') return false;
}
return true;
}
void backtracking(int n, int row, vector<string>& temp){
if(row == n){
result.push_back(temp);
return;
}
for(int i=0; i<n; i++){
if(isValid(i, row, temp, n)){
temp[row][i] = 'Q';
backtracking(n, row+1, temp);
temp[row][i] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
result.clear();
vector<string> temp(n, string(n, '.'));
backtracking(n,0, temp);
return result;
}
};
参考文章:代码随想录- 51. N皇后
37. 解数独
class Solution {
public:
bool isValid(int row, int col, char val, vector<vector<char>>& board){
for(int i=0; i<board.size(); i++){
if(board[i][col]==val){
return false;
}
}
for(int j=0; j<board.size(); j++){
if(board[row][j]==val){
return false;
}
}
int row_s = (row/3)*3;
int col_s = (col/3)*3;
for(int i = row_s; i<row_s+3; i++){
for(int j=col_s; j<col_s+3; j++){
if(board[i][j]==val){
return false;
}
}
}
return true;
}
bool backtracking(vector<vector<char>>& board){
for(int i=0; i<board.size(); i++){
for(int j=0; j<board.size(); j++){
if(board[i][j] == '.'){
for(char val='1'; val<='9'; val++){
if(isValid(i,j,val, board)){
board[i][j]=val;
if(backtracking(board)) return true;
board[i][j]='.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
参考文章:代码随想录- 37. 解数独