7.电话号码的字母组合OJ链接

map hashTable={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
class Solution {
public:void DFS(string& digits,vector&resultString,string curStr,int curDepth){//如果此时遍历到最后一个if(curDepth==digits.size()){resultString.push_back(curStr);return;}//利用哈希映射的方式进行string strMap=hashTable[digits[curDepth]];for(char ch:strMap){DFS(digits,resultString,curStr+ch,curDepth+1);}}vector letterCombinations(string digits) {//将所有的结果集保存到resultStringvector resultString;if(digits.empty())return resultString;//从第一个位置开始进行深度优先遍历深度优先遍历DFS(digits,resultString,"",0);return resultString;      }
};

8.组合总和OJ链接

class Solution {
public:void DFS(vector&candidates,vector>&solutions,vector&solution,int curSum,int position,int target){//如果当前遍历所得到的结果刚好为所给的target值//那么将当前所遍历的结果集保留在solutionsif(curSum==target){solutions.push_back(solution);}   //如果遍历出的和是大于，则说明此时条件不满足if(curSum>target){return;}//从position位置开始进行深度优先遍历操作for(int i=position;itarget)//如果此时的所给出的candidats中// //的值比所给的target大，那么直接结束当前所在位置的优先遍历{continue;}//不满足上述条件说明此时的curSum的值小于target//可以将当前的candidates[i]放入到当前的结果集中//然后接着往后进行深度优先遍历操作solution.push_back(candidates[i]);DFS(candidates,solutions,solution,curSum+candidates[i],i,target);solution.pop_back();}}vector> combinationSum(vector& candidates, int target) {//定义一个二维数组保留所有结果集vector> solutions;//保留当前的结果集vector solution;//记录当前结果集中的和int curSum=0;//进行深度优先遍历DFS(candidates,solutions,solution,curSum,0,target);return solutions;}
};

9.活字印刷OJ链接

class Solution {
public:void DFS(string &tiles,string curStr,vector&useString,unordered_set&hashTable){//如果此时深度优先遍历的字符串不为空，则此时的所得到的的字符串放入当前的哈希表中，将自动进行去重的处理if(!curStr.empty())hashTable.insert(curStr);//深度优先遍历每一个位置for(int i=0;i hashTable;//先将当前的tiles进行初始化的操作vector useString(tiles.size(),0);//进行深度优先遍历操作DFS(tiles,"",useString,hashTable);return hashTable.size();}
};

10.N皇后OJ链接

class Solution {
public://深度优先遍历void DFS(vector>>&solutions,vector>&solution,int curRow,int n){//如果当前行等于n则将一种solution方案放入solutions中if(curRow==n){solutions.push_back(solution);}for(int i=0;i>&solution,int curRow,int col){//遍历方案中的点//如果此时该皇后中的纵坐标与方案中的纵坐标相同或者横坐标与纵坐标的和等于当前皇后的横纵坐标之和或者是方案中横纵坐标之差等于当前皇后的横纵坐标之差for(auto i:solution){if(i.second==col||i.first+i.second==curRow+col||i.first-i.second==curRow-col){return false;}}return true;}vector> transformString(vector>>&solutions,int n){vector> resultString;//保留最后方案中的字符串for(vector>&solution:solutions){//利用构造函数先进行所有的字符变为'.'最后再将皇后位置变为'Q'vector tmpString(n,string(n,'.'));for(pair &i:solution){tmpString[i.first][i.second]='Q';}resultString.push_back(tmpString);}return resultString;}vector> solveNQueens(int n) {vector>> solutions;//将不同解法的方案存放vector> solution;//存放一种方案中的n个皇后的摆放//将n*n的棋盘从第一个位置开始进行深度优先遍历DFS(solutions,solution,0,n);//将深度优先遍历后的每一种方案都转化为字符型return transformString(solutions,n);}
};

11.N皇后IIOJ链接

class Solution {
public://深度优先遍历int  DFS(vector>&solution,int curRow,int n){//如果当前行等于n则将一种solutionif(curRow==n){return 1;}else{int count=0;for(int i=0;i>&solution,int curRow,int col){//遍历方案中的点//如果此时该皇后中的纵坐标与方案中的纵坐标相同或者横坐标与纵坐标的和等于当前皇后的横纵坐标之和或者是方案中横纵坐标之差等于当前皇后的横纵坐标之差for(auto i:solution){if(i.second==col||i.first+i.second==curRow+col||i.first-i.second==curRow-col){return false;}}return true;}int totalNQueens(int n) {vector> solution;return DFS(solution,0,n);}
};

二、有关广度优先遍历的题型

1.N叉树的层序遍历OJ链接

/*
// Definition for a Node.
class Node {
public:int val;vector children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector> levelOrder(Node* root) {if(root==nullptr) return vector>();vector> vv;queue q;//利用队列进行广度优先遍历q.push(root);//首先将头结点先入队操作while(!q.empty())//如果此时的队列不为空，则继续进行操作{vector v;//利用一个一维数组来存储当前层的节点int size=q.size();//每一层的大小需要保存下来，方便下一次的遍历操作for(int i=0;ival);for(auto child:front->children)//遍历当前节点的孩子节点，如果不为空，则将此时的孩子节点入队列if(child)q.push(child);}vv.push_back(v);}return vv;}
};

2.腐烂的橘子OJ链接

int nextp[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
class Solution {
public:int orangesRotting(vector>& grid) {//利用pair来存储位置信息queue> q;int row=grid.size();int col=grid[0].size();//第一步将腐烂的橘子进行入队操作for(int i=0;i Curpos=q.front();q.pop();for(int i=0;i<4;i++){int newX=Curpos.first+nextp[i][0];int newY=Curpos.second+nextp[i][1];//如果此时的位置中存在越界或者是该位置上面的橘子已经被腐烂过则跳过此次if(newX>=row||newY>=col||newX<0||newY<0||grid[newX][newY]!=1)continue;flag=1;grid[newX][newY]=2;q.push(make_pair(newX,newY));}}if(flag)++times;}//最后需要进行判断是否还存在无法腐烂的橘子for(int i=0;i

class Solution {
public:int ladderLength(string beginWord, string endWord, vector& wordList) {//利用哈希表进行查找效率比较高unordered_set HashTable(wordList.begin(),wordList.end());//定义一个标记的哈希表来标记已经查找过的单词unordered_set visitHashTable;//讲起始的单词进行标记visitHashTable.insert(beginWord);//利用队列的特性进行广度优先遍历操作queue q;q.push(beginWord);int step=1;//队列不为空，继续进行转换操作while(!q.empty()){int size=q.size();for(int i=0;i

class Solution {
public:int minMutation(string startGene, string endGene, vector& bank) {//利用哈希表查找unordered_set HashTable(bank.begin(),bank.end());//标记unordered_set visitHashTable;visitHashTable.insert(startGene);//利用队列进行广度优先遍历操作queue q;q.push(startGene);//对于基因有四种可能vector Gene(4);Gene[0]='A';Gene[1]='C';Gene[2]='G';Gene[3]='T';int step=0;while(!q.empty()){int size=q.size();for(int i=0;i

class Solution {
public:int openLock(vector& deadends, string target) {//利用哈希表的查找unordered_set HashTable(deadends.begin(),deadends.end());if(HashTable.find("0000")!=HashTable.end())return -1;//标记已经搜索过的字符串unordered_set visitHashTable;visitHashTable.insert("0000");//利用队列进行广度优先遍历queue q;q.push("0000");int step=0;while(!q.empty()){int size=q.size();for(int i=0;i