一：优美的排列

题目：

有1~n的n个整数，用这些数构造一个数组perm，只要构造的数组满足以下两个条件：

（1）i可以被perm[i]整除

（2）perm[i]可以被i整除

返回其能构造出的优美数组的个数

方法：

1：画出决策树

2：算法原理

类似于全排列的思路，不过不需要path数组，只需要统计优美排列的个数即可

全局变量

int ret;（总共的个数）

bool check[]；（当前数字是否已被使用）

dfs函数

dfs(int pos, int n)；

class Solution {int ret;//记录总的个数bool check[16];//当前位置的数是否被使用
public:int countArrangement(int n) {dfs(1,n);//后一个为path,记录当前的数return ret;}void dfs(int pos,int n){if(pos==n+1){ret++;return;}for(int i = 1;i<=n;i++){if(check[i]==false&&(pos%i==0||i%pos==0)){check[i] = true;dfs(pos+1,n);check[i] = false;}}}
};

二：N皇后

题目：

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

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

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

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

方法：

1：画出决策树

2：算法原理

如何进行剪枝，提高代码效率是重点

基本思路：从每一行开始进行递归，在每一行的时候又从每一列开始进行判断可否加上皇后

剪枝（考虑当前的位置是否可以放上皇后）：

（1）无脑循环

（2）类似于哈希表

每一列都只能有一个皇后，可以用一个函数标记当前列的位置是否有皇后；

主对角线上和副对角线上也只能有一个皇后，同样可以利用同一对角线上满足一次线性函数的特性，进行标记和后续判断；

全局变量：

vector<vector<string>> ret;（记录全部有效的排列）

vector<string> path;（记录当前这一条的排列方法）

bool checkCol[];（判断当前列是否可以已有皇后）

bool checkDig1[];（判断主对角线上是否已有皇后）

bool checkDig2[];（判断副对角线是否已有皇后）

int n;（棋牌的规格）

代码一些方法：

先将path全部初始化为‘.’，方便之后直接进行皇后的添加

class Solution {bool checkCol[10];//这一列是否有皇后bool checkDig1[20];bool checkDig2[20];vector<vector<string>> ret;vector<string> path;int n;
public: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(row==n){ret.push_back(path);return;}for(int col = 0;col<n;col++){if(!checkCol[col]&&!checkDig1[row-col+n]&&!checkDig2[row+col]){path[row][col] = 'Q';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = true;dfs(row+1);path[row][col] = '.';checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = false;}}}
};

三：有效的数独（本道题不牵扯回溯，主要利用哈希表的知识）

题目：

判断一个9*9的的数独是否有效，要有效需要满足以下的规则：

（1）数字1~9在每一行只出现一次；

（2）数字1~9在每一列只出现一次；

（3）数字1~9在每一个以粗实线分割的3*3宫内只出现一次

方法：

全局变量：

bool row[][];（标记一行的数，看是否有重复）

bool col[][];（标记一列的数，看是否有重复）

bool grid[][][];（三维数组，解决3*3宫内数不重复的问题）

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0;i<9;i++)for(int j = 0;j<9;j++){if(board[i][j]!='.'){int num = board[i][j] - '0';//是否有效if(row[i][num]||col[j][num]||grid[i/3][j/3][num])return false;row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}return true;}};

四：解数独

题目：

编写一个程序，通过填充空格来解决数独问题，需要满足以下规则：

（1）数字1~9在每一行只出现一次；

（2）数字1~9在每一列只出现一次；

（3）数字1~9在每一个以粗实线分割的3*3宫内只出现一次

方法以及思路：

同有效数独这一题全局变量一致，需要三个来标记当前位置的bool数组

需要先将数独遍历一遍，将那三个数组初始化，接着再进行dfs函数的设计

在dfs函数中，需要将数独进行遍历，然后在空的位置，将1~9这几个数字判断一下是否可以填进去，之后因为只存在唯一的一个解法，所有还要对当前位置没有数字可以填进的情况，直接返回false，避免程序出现bug。

dfs函数设计：bool dfs(vector<vector<char>>& board)

class Solution {bool row[9][10],col[9][10],grid[3][3][10];
public: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 num = board[i][j] - '0';row[i][num] = col[j][num]  =grid[i/3][j/3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j]=='.'){//填数for(int num = 1;num<=9;num++){if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num]){board[i][j] = '0'+num;row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board)==true)  return true;//恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;}}}return true;}
};