递归和回溯
例题17：
给你一个数字的字符串，返回这个数字字符串能表示的所有字母组合
如对数字字符串“2，3”
{a,b,c} {d,e,f}
-字符串的合法性
-空字符串
-多个解的顺序
class Solution {
private:
const string letterMap[10]= {
" ", //0
"", //1
"abc", //2
"def",//3
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
vector <string> res;
void findCombination(const string &digits,int index,const string &s){
//s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
//寻找和digits[index]匹配的字母，获得digits[0....index]翻译得到的解
if(index==digits.size()){
//保存s
res.push_back(s);
return;
}
char c = digits[index];
//每次处理数字字符串中的一位，赋值给char c
assert(c>='0'&&c<='9'&&c!='1');
string letters = letterMap[c -'0'];
//为ASCII字符中的数字（‘123456’）想转换为纯数字（1,2,3,4...）就要减去48（ASCII单位），
//而‘0’的ASCII单位正好等于48。
for(int i = 0;i<letters.size();i++)
findCombination(digits,index+1,s+letters[i]);
//这里也是递归思想，假设数字为“3，2”，所对应for循环三次，下一次递归的“2”也对应for循环三次
return;
}
public:
vector<string> letterCombinations(string digits){
res.clear();
if(digits == "")
return res;
findCombination(digits,0,"");//初始化
return res;
}
};例题93
例题131
回溯算法的应用
例题46
给定一个整型数组。其中每一个元素都各不相同，返回这些元素所有排列的可能
class Solution {
private:
vector<vector<int>>res;
vector<bool> used;
//bool类型的数组使得每个index的元素只能使用一次
void generatePermutation(const vector<int>nums,int index,vector <int> &p){
if(index == nums.size()){
res.push_back(p);
return;
}
for(int i =0;i<nums.size();i++)
if(!used[i]){
p.push_back(nums[i]);
used[i] = true;
generatePermutation(nums,index+1,p);
//这里当num[i]作为排列组合的首位元素，所进行的全部组合完成时需要弹出这个元素，让这个元素之后也可以在排列组合的其他位置继续使用
p.pop_back();
used[i] = false;
}
return;
}
public:
vector<vector<int>> permute(vector<int> &nums){
res.clear();
if(nums.size() == 0)
return res;
vector<int>p;
used = vector<bool>(nums.size(),false);
//初始化使得nums.size()个数的元素都为false
generatePermutation(nums,0,p);
return res;
}
};例题47
例题77
class Solution {
private:
vector<vector<int>>res;
//排列组合C(n,k)
void generateCombinations(int n,int k,int start,vector<int> &c){
if(c.size() == k){
res.push_back(c);
return;
}
for(int i = start;i<=n;i++){
c.push_back(i);
generateCombinations(n,k,i+1,c);
c.pop_back();
}
return;
}
public:
vector<vector<int>>combine(int n,int k){
res.clear();
if(n<=0||k<=0||k>n)
return res;
vector<int> c;
generateCombinations(n,k,1,c);
return res;
}
};回溯法的剪支
class Solution {
private:
vector<vector<int>>res;
//排列组合C(n,k)
void generateCombinations(int n,int k,int start,vector<int> &c){
if(c.size() == k){
res.push_back(c);
return;
}
for(int i = start;i<=n-(k-c.size())+1;i++){
c.push_back(i);
generateCombinations(n,k,i+1,c);
c.pop_back();
}
return;
}
public:
vector<vector<int>>combine(int n,int k){
res.clear();
if(n<=0||k<=0||k>n)
return res;
vector<int> c;
generateCombinations(n,k,1,c);
return res;
}
};例题39：Combination Sum
例题40：Combination Sum II
例题216
例题78
例题401
例题79 Word Search
class Solution {
private:
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//偏移数组 ，类似深度学习
int m,n;
vector<vector<bool>> visited;
bool inArea(int x,int y){
return x>=0 && x<m && y>=0 && y<n;
}
bool searchWord(const vector<vector<char>> &board,const string &word,int index,int startx,int starty){
if(index == word.size()-1) //索引index到达要求的字符串末尾
return board[startx][starty] == word[index];
//直接去比较二维数组和word[index]
if(board[startx][starty] == word[index]){
visited[startx][starty] = true;//初始化为true
//从startx,starty出发，四个方向寻 找
for(int i=0;i<4;i++){
int newx = startx +d[i][0];
int newy = starty +d[i][1];
if(inArea(newx,newy) && !visited[newx][newy])
if(searchWord(board,word,index+1,newx,newy))
return true;
}
//回溯
visited[startx][starty] = false;
}
return false;
}
public:
bool exist(vector<vector<char>> &board,string word){
m = board.size(); //行
assert(m>0);
n = board[0].size(); //列
// 初始化visited 制作一个m行n列的bool vector
visited = vector<vector<bool>>(m,vector<bool>(n,false));
for(int i =0;i<board.size();i++)
for(int j=0;j<board[i].size();j++)
if(searchWord(board,word,0,i,j)) //bool函数有返回值，根据返回值 判断最终的true or False
return true;
return false;
}
};floodfill 算法
例题200
class Solution {
private:
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
//偏移数组 ，类似深度学习
int m,n;
vector<vector<bool>> visited;
bool inArea(int x,int y){
return x>=0 && x<m && y>=0 && y<n;
}
// 保证(x,y)合法 grid[x][y]时未访问的
void dfs(vector<vector<char>> &grid,int x,int y){
visited[x][y] = true;
for(int i = 0;i<4;i++){
int newx = x+d[i][0];
int newy = y+d[i][1];
if(inArea(newx,newy) && !visited[newx][newy]&& grid[newx][newy] == '1')
dfs(grid,newx,newy);
}
return;
}
public:
int numIslands(vector<vector<char>> &grid){
m = grid.size();
if(m == 0)
return 0;
n = grid[0].size();
visited = vector<vector<bool>>(m,vector<bool>(n,false));
int res = 0;
for(int i = 0;i<m;i++)
for(int j = 0;j<n;j++)
if(grid[i][j] == '1' && !visited[i][j]){
res++;
//找到一个陆地，假设这是一个独立的岛屿，然后根据dfs去将和它相连的陆地都标记为true。这样在寻找下一个岛屿的时候，这些标记为true的陆地不会被选择
dfs(grid,i,j);
}
return res;
}
};例题130
例题417
回溯法是经典人工智能的基础
例题51 N-queens
class Solution {
private:
vector<bool>col,dia1,dia2;
//去给定界定条件，列，对角线
vector<vector<string>> res;
void putQueen(int n,int index,vector<int> &row){
if(index == n){
res.push_back(generateBoard(n,row));
return ;
}
for(int i=0;i<n;i++)
//尝试将index行的皇后摆放在第i列
//如果满足皇后条件
if(!col[i] && !dia1[index+i] && !dia2[index-i+n-1]){
row.push_back(i);
//将每行的列位置推进row
col[i] = true;
dia1[index+i] = true;
dia2[index-i+n-1] = true;
putQueen(n,index+1,row);
/*
递进循环到某一个位置时如果寻找不到有效位置，则进行回溯，尝试将之前某index行的皇后换成其他位置摆放
*/
col[i] = false;
dia1[index+i] = false;
dia2[index-i+n-1] = false;
row.pop_back();
}
return;
}
vector<string> generateBoard(int n,vector<int> &row){
assert(row.size() == n);
vector<string>board(n,string(n,'.'));
for(int i = 0;i<n;i++)
board[i][row[i]] = 'Q';
//row[]是4个数字，对应四个列方向的索引，board[][]替换成Q
return board;
}
public:
vector<vector<string>> solveNQueens(int n){
res.clear();
col = vector<bool>(n,false);
dia1 = vector<bool>(2*n-1,false); //对角线个数2n-1
dia2 = vector<bool>(2*n-1,false);
vector<int> row;
putQueen(n,0,row);
return res;
}
};例题52
例题37
求解数独
