html5 微网站布局,嘉兴网站,网站建设人员招聘要求,做网站入门目录
一、递归
1.什么是递归#xff1f;
2.什么时候使用递归#xff1f;
3.如何理解递归#xff1f;
4.如何写好递归#xff1f;
二、记忆化搜索#xff08;记忆递归#xff09;
三、回溯
四、剪枝
五、综合试题
1.N皇后
2.解数独 DFS也就是深度优先搜索
2.什么时候使用递归
3.如何理解递归
4.如何写好递归
二、记忆化搜索记忆递归
三、回溯
四、剪枝
五、综合试题
1.N皇后
2.解数独 DFS也就是深度优先搜索比如二叉树的前中后序遍历都属于DFS。其本质是递归要学好DFS首先需要掌握递归。接下来咱们就一起来学习DFS涉及的算法。
一、递归
1.什么是递归
递归可以这样理解把它拆分出来两个字“递”和“归” 递递推这就需要找到递推公式 归回归需要找到回归条件递推过程逐渐逼近回归条件
直白一点来说就是一个函数自己调用自己的情况当然一定是要能够返回的。
二叉树的遍历快排归并中都用到了递归。
2.什么时候使用递归 满足以下条件通常都能使用递归解决在主问题中能找到相同的子问题在子问题中又能找到相同的子问题。 注意递归过程也就是在前一个函数没有销毁的时候调用下一个相同函数调用函数就需要开辟函数栈帧会占用大量空间所以递归层数太多会导致栈溢出解决不了问题。 缺点递归算法会占用大量内存有栈溢出的风险在实际开发中要尽量减少递归算法的使用。 优点递归算法简单明了容易被想到代码也是非常的好写。 3.如何理解递归 在开始学递归时还是需要去分析递归展开细节图的这个可以让我们理解递归的工作原理理解为什么递归能解决问题。当我们在逻辑上有了自洽后。就再也不要去管递归展开图如果一味地去纠结递归展开图只会让我们越来越晕。 相反我们需要从宏观的角度看待递归问题把递归函数看作一个黑盒并且相信这个黑盒一定能够帮我们完成任务。
4.如何写好递归
写好递归只需要做好下面这几步
1.找到相同的子问题 -- 解决函数头的设计。2.只关心某个子问题是如何解决的 -- 解决函数体的书写。3.处理递归函数的出口 -- 返回值的确定。 我们可以知道相同的子问题中的“相同”指的是逻辑相同而不同的只有操作对象所以在设计函数头的参数列表时只需要让这些不同的操作对象能够参入即可。
所以我们做这样一个函数头
void _hanota(vectorint A, vectorint B, vectorint C,int n)
表示把A柱中n个盘子移动到C柱B是辅助用的柱子。 提示这里大家可能会有一个疑惑为什么传入的参数是几个盘子而不是哪几个盘子。其实是因为游戏规则本来就是只能从上往下依次从柱子取盘。 所以知道要取一个盘子也就能确定哪几个盘子它们是一对一的关系。
单个子问题的解决我放在代码中讲解如下
class Solution {
public:void _hanota(vectorint A, vectorint B, vectorint C,int n){if(n1)//只需要移动一个盘的时候直接操作{C.push_back(A.back());A.pop_back();return;}//先把A中n-1个盘移动到B中_hanota(A,C,B,n-1);//在把剩下一个盘移动到C中C.push_back(A.back());A.pop_back();//最后再把B中的n-1个盘移动到C中_hanota(B,A,C,n-1);}void hanota(vectorint A, vectorint B, vectorint C) {//题目通过的参数列表无法满足我们的需求重写一个函数来解决。_hanota(A,B,C,A.size());}
};
二、记忆化搜索记忆递归
通过下面这个题我会引出记忆化搜索。 以上是一个爬楼梯问题我们通过找规律来解决问题。 楼顶数1 2 3 4 5 6 方法数1 2 3 5 8 13 通过观察发现楼顶数x与方法数F( x )的关系为 出现这样一个递推公式我们第一想到的就是递归来实现。
1.递归代码
int F(int n)
{if(n2) return n;else return F(n-1)F(n-2);
}
注意这里为了方便说明问题函数名我直接使用F这和原题提供的函数名不一样。
下面是对以上代码的递归展开图进行剖析
红线为递推过程绿线为回归过程。 接下来是复杂度分析 时间复杂度为O(2^n)空间复杂度为O(n) 通过观察我们发现出现很多重复计算的地方图中画圈颜色相同的地方如果减少这些重复计算的地方那么效率会提高很多。为了解决这个问题我们想象一下把每次计算的数据存起来下次用到的时候就不用计算直接返回。而这就是记忆递归。
2.记忆递归
int arr[46]{0};//通过题目确定数据范围
F(int n)
{if(n2) return n;if(arr[n]!0) return arr[n];else return arr[n]F(n-1)F(n-2);
} 创建一个数组并初始值为零把每次返回的值存在数组里这样可以避免重复计算判断a[n]为非0则直接返回。时间复杂度为O(n),空间复杂度为O(n)。
通常能使用记忆递归解决的问题都能转化为动态规划如下
3.动态规划
int F(int n){int dp[46]{0};dp[1]1,dp[2]2;for(int i3;in1;i)dp[i]dp[i-1]dp[i-2];return dp[n];
} 把1到n每个楼顶对应的方法数存入数组中用前两个来计算后一个直到推到n此方法相比以上方法减少了递归带来的内存申请时间复杂度为O(n)空间复杂度为O(1)。
好题推荐329. 矩阵中的最长递增路径 - 力扣LeetCode
三、回溯 回溯又叫作“恢复现场”它是基于递归的一种算法是为了解决搜索时路径之间的信息互相干扰的问题。如下 回溯的具体用法我们来从下面这个题中感受。 在做搜索题的时候最重要的莫过于就是决策树的设计。如果决策树做得清晰明了那么代码也就好写了。 什么是决策树在搜索过程中它抽象出来的必定是一棵树形结构而这棵树是如何展开的我们在设计展开逻辑的过程也就是在做一颗决策树。如下 class Solution {
public:vectorvectorint ret;//统计结果vectorint path;//记录路径vectorvectorint subsets(vectorint nums){dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){if(posnums.size())//即到达叶子节点{ret.push_back(path);return;}//不选该元素直接进入下一元素的选择dfs(nums,pos1);//选择该元素并进入下一元素的选择path.push_back(nums[pos]);dfs(nums,pos1);//函数退出之前先把该层的数据清除回溯path.pop_back();}
};
其实这里回溯思想就一句代码即path.pop_back()。回溯就这么简单。 我们看一看没有回溯的决策树 这里以叶子节点3开始画回归路线蓝线回归红线递推。 我们可以看到如果不把[3]这一节点的信息清除的话它会把信息带到上一层然后一直往下带每一节点都不恢复现场就会使每个节点都带上一个信息往回传导致结果错误。所以回溯算法在很多场景都是至关重要的。 当然决策树并不是唯一的每个人画的可能都不一样比如还可以这样 不同的决策树代码也是不同的如下
class Solution
{
public:vectorvectorint ret;vectorint path;vectorvectorint subsets(vectorint nums){_subsets(nums,0);return ret;}void _subsets(const vectorint nums,int pos){ret.push_back(path);for(int ipos;inums.size();i){path.push_back(nums[i]);_subsets(nums,i1);path.pop_back();//恢复现场}}
};
四、剪枝 剪枝可以这么理解如果我们已知某条枝干没有正确答案或某条枝干是错误的那么我们就不进行搜索这样可以减少不必要的搜索提高效率。具体我们可以从题中感受。 这个题放在小学数学就是一个画树状图的题我们直接开始吧。 如上这颗决策树在一条路径中如果一个元素选过一次那么下次就不能再选需要把它剪掉。我们可以使用一个哈希表来记录某个元素是否出现过。但在该过程中同样需要注意“恢复现场”。
class Solution {
public:vectorint path;vectorvectorint ret;int n;vectorvectorint permute(vectorint nums){n nums.size();vectorbool hash(n);dfs(nums,hash);return ret;}void dfs(vectorint nums,vectorbool hash){if(path.size()n){ret.push_back(path);return;}for(int i0;in;i){if(hash[i]) continue;//剪枝hash[i]true;path.push_back(nums[i]);dfs(nums,hash);hash[i]false;path.pop_back();}}
};
同样的这里剪枝就一句代码即 if(hash[i]) continue。剪枝就这么简单。
五、综合试题
1.N皇后 首先我们还是一样的试着把决策树画出来如下 这样我们可以知道这个题解题框架。接下来就是处理如何剪枝的问题。 题目要求一个棋子的横排竖排斜对角 反斜对角都不能有其他棋子那么这就好办只需要使用4个哈希表来记录这些位置是否已有棋子如果有那就不能放直到遍历完所以格子还是无法将棋子放入则该条路径行不通。 class Solution {
public:vectorvectorstring ret;vectorstring path;vectorbool row,col,bias1,bias2;vectorvectorstring solveNQueens(int n){row.resize(n,false),col.resize(n,false);bias1.resize(2*n-1,false),bias2.resize(2*n-1,false);for(int i0;in;i) path.push_back(string(n,.));dfs(0,n);return ret;}void dfs(int pos,int n){if(posn){ret.push_back(path);return;}for(int j0;jn;j){//剪枝if(row[pos]||col[j]||bias1[posj]||bias2[n-posj-1]) continue;row[pos]col[j]bias1[posj]bias2[n-posj-1]true;path[pos][j]Q;dfs(pos1,n);//恢复现场回溯row[pos]col[j]bias1[posj]bias2[n-posj-1]false;path[pos][j].;}}
};
2.解数独 同样我们需要画出决策树我们可以直接暴力搜索每一个空缺的位置再在每一个空位暴力枚举每一个数字即可。如下 在此过程中我们需要注意剪枝与回溯的问题为了检查数字的合法性还需要我们记录每一行每一列每个3*3小方格中的某个数字是否出现过。所以需要3个哈希表。
由题可知行数列数都是固定的为9行9列。 所以可以用 bool row[9][10] bool col[9][10]来作为哈希表记录某一行的某个数字是否出现过。
使用bool hash[3][3][10]来作为哈希表记录某一个3*3宫格的某个数字是否出现过。
代码示例
class Solution
{
public:bool row[9][10],col[9][10],hash[3][3][10];void solveSudoku(vectorvectorchar board){//初始化哈希表for(int i0;i9;i){for(int j0;j9;j){if(board[i][j].) continue;int keyboard[i][j]-0;row[i][key]col[j][key]hash[i/3][j/3][key]true;}}dfs(board);}bool dfs(vectorvectorchar board){for(int i0;i9;i){for(int j0;j9;j){if(board[i][j]!.) continue;for(int key1;key9;key){if(row[i][key]||col[j][key]||hash[i/3][j/3][key]) continue;//剪枝board[i][j]key0;row[i][key]col[j][key]hash[i/3][j/3][key]true;if(dfs(board)) return true;//剪枝//恢复现场board[i][j].;row[i][key]col[j][key]hash[i/3][j/3][key]false;}return false;}}return true;}
};
好题推荐
39. 组合总和 - 力扣LeetCode
22. 括号生成 - 力扣LeetCode
1219. 黄金矿工 - 力扣LeetCode
77. 组合 - 力扣LeetCode
