美食网站建设背景拘束 wordpress

当前位置： 首页 > news >正文

美食网站建设背景,拘束 wordpress,小程序模板设计,网站建设与维护前景目录 搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜 1.深度优先遍历 vs 深度优先搜索(dfs) 2.宽度优先遍历 vs 宽度优先搜索(bfs) 2.关系图暴力枚举一遍所有的情况 3.拓展搜索问题全排列 决策树

1. 计算布尔⼆叉树的值#xff08;medi…目录 搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜 1.深度优先遍历 vs 深度优先搜索(dfs) 2.宽度优先遍历 vs 宽度优先搜索(bfs) 2.关系图暴力枚举一遍所有的情况 3.拓展搜索问题全排列 决策树
2. 计算布尔⼆叉树的值medium 解析 1.函数头 2.函数体 3.函数出口 总结
3. 求根节点到叶节点数字之和medium 解析​编辑 总结
4. ⼆叉树剪枝medium 总结
5. 验证⼆叉搜索树medium 解析 策略一中序遍历判断这个二叉树是否有序 策略二剪枝 总结
6. ⼆叉搜索树中第 k ⼩的元素medium 解析 总结
7. ⼆叉树的所有路径easy 解析 总结 穷举vs暴搜vs深搜vs回溯vs剪枝 什么是回溯算法
8. 全排列medium 解析 1暴力枚举 2递归优化 2.设计代码 全局变量 dfs函数 细节问题 总结
9. ⼦集medium 解析 解法一 1.决策树 2.设计代码 全局变量 dfs 解法二 1.画决策树 2.设计代码 总结 搜索 vs 深度优先遍历 vs 深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜 1.深度优先遍历 vs 深度优先搜索(dfs) 2.宽度优先遍历 vs 宽度优先搜索(bfs) 那么遍历只是形式目的是搜索 2.关系图 暴力枚举一遍所有的情况 搜索(暴搜) dfs 3.拓展搜索问题 全排列 决策树 废话不多说直接进入例题  
10. 计算布尔⼆叉树的值medium 题目比较长但是还是比较好理解的0123分别代表falsetrue,|, 然后在这这个决策树上通过运算算出最后这颗树的结果 解析 递归函数的调用 主要就是分三步当主问题与子问题相同的时候 1.函数头 2.函数体 3.函数出口 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:bool a[2]{false,true};bool evaluateTree(TreeNode root) {if(root-leftnullptr||root-rightnullptr) return a[root-val];bool leftevaluateTree(root-left);bool rightevaluateTree(root-right);return root-val2?left|right:leftright;} }; 总结 只要能分析出当前问题的相同子函数就可以得出函数体里面的内容通过所有相同的子函数的内容进行一步步操作就能完成当前函数的任务。 2. 求根节点到叶节点数字之和medium 题意还是比较好理解的就是对从根节点开始一直到叶子节点计算每个节点当前值不断10最后所有叶子节点的和 解析 这种题目计算每个叶子节点的方法一眼就是dfs先递归到叶子节点然后就开始相加。 以下是同一种dfs的两种思想 1.定义全局变量ret然后每次递归到叶子节点的时候就开始进行相加那么我就是用一个字符串s来保存每一层的临时变量这样可以达到回溯的效果起始不要字符串保存只有用presum来存储临时变量也是ok的都能存的下最终的和然后每次到叶子节点ret就进行相加知道加完所有叶子节点的值就完成返回ret 唯一需要注意的就是在传入dfs的时候就要立刻加上当前节点的值这样就不会漏掉当前节点的某一位因为只要到叶子节点就要开始返回上一层了为了防止叶子节点的值给漏掉。 /** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:int ret0;int sumNumbers(TreeNode root) {string s;dfs(root,s);return ret;}void dfs(TreeNode* root,string s){sto_string(root-val);if(root-leftnullptrroot-rightnullptr){retstoi(s);return;}if(root-left) dfs(root-left,s);if(root-right) dfs(root-right,s);} }; 2.就是用presum来记录临时变量不需要字符串到整形整形到字符串的各种转换因为最后的结果int也能存下。 看到上面的图就能看出如果我存临时变量presum那么dfs返回的就是当前节点下所有叶子节点的和那么整个二叉树就都变成了一个子问题就是要求头节点下所有叶子节点的和。 函数头int dfs(root,presum); 出口就是当到达叶子节点的时候那么就返回当前叶子节点的presum 函数体用ret来记录当前节点下所有左右子树中叶子节点的和在当前节点左子树不为空下传入dfs(root-left,presum);在当前节点右子树不为空下传入dfs(root-right,presum);来求出当前节点下的左右子树的所有叶子节点的和 最后返回ret /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:int sumNumbers(TreeNode root) {return dfs(root,0);}int dfs(TreeNode* root,int presum){presumpresum10root-val;if(root-leftnullptrroot-rightnullptr) return presum;int ret0;//记录当前节点下所有叶子节点的值if(root-left) retdfs(root-left,presum);if(root-right) retdfs(root-right,presum);return ret; //返回给上一层} }; 总结 像这种带有回溯类的问题只需要考虑清楚带上的临时变量不会再中途被改变并且再返回上一层稳定即可。 3. ⼆叉树剪枝medium
    本题题意比较绕但是就是删掉所有子树全为0的节点 解析 因为计算机不可能知道当前节点下左右子树的所有节点是否全为0所以就要完全遍历到叶子节点在开始判断判断叶子节点是否为0 如果是就直接置为空并且返回空否则就返回当前节点不改变。 经过上面的思考发现要先解决完所有的左子树和右子树然后在考虑当前的节点是否为0且左右子树是否为空所以就完全是一个后序遍历。 1.函数头再前面的分析里面要返回当前节点的情况是否为空否则就返回当前节点。说明函数头是带有返回值的。 Node dfs(root); 2.函数体 由于是后序遍历先访问所有左子树再访问右子树。然后进行判断当前节点 root-leftdfs(root-left); root-rightdfs(root-right); 判断如果当前节点的左右子树都为空并且当前节点值为0就说明这个节点也可以被删掉 if(root-leftnullptrroot-rightnullptrroot-val0) rootnullptr return root;//将当前节点的值返回给上一层 3.递归出口当前节点为空的时候就返回空 if(rootnullptr) return nulltpr; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:TreeNode pruneTree(TreeNode* root) {if(rootnullptr) return nullptr;root-leftpruneTree(root-left);root-rightpruneTree(root-right);if(root-leftnullptrroot-rightnullptrroot-val0) rootnullptr; return root;//返回给上一层} }; 总结 写的代码很简单但是要想清楚每一步还是很不容易多注意细节问题多思考一个题目要反复思考才能被吸收。 4. 验证⼆叉搜索树medium 题意很简单只要证明该树是不是二叉搜索树 解析 策略一中序遍历判断这个二叉树是否有序 用prev来记录二叉树的中序的根节点就是当前节点左子树的最右边的一个节点 要保证该二叉树是平衡二叉树就要一直保证prev root-val 那么就能满足条件一旦打破了就返回false 那么 1.函数头bool dfs(root) 2.函数体 弄弄左子树bool leftdfs(root-left); 中序判断bool ret false;                   if(prevroot-val) rettrue;                   prev root-val; 弄弄右子树bool rightdfs(root-right); 3.出口条件 当节点访问到空的时候证明没有问题返回true /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:long prevLONG_MIN;bool isValidBST(TreeNode root) {if(rootnullptr) return true;bool leftisValidBST(root-left);bool retfalse;if(root-valprev) rettrue;prevroot-val;bool rightisValidBST(root-right);return leftrightret;} }; 策略二剪枝 上面策略一是访问了所有的节点但是如果只要满足有一个节点不满足平衡二叉树的条件不满足升序那么就要返回false不在往后遍历。 那么只需要再判断左子树的时候证明他是false 或者 再判断当前值不满足升序的时候都返回false就能完成剪枝操作不在往后执行 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:long prevLONG_MIN;bool isValidBST(TreeNode root) {if(rootnullptr) return true;bool leftisValidBST(root-left);if(leftfalse) return false;bool retfalse;if(root-valprev) rettrue;prevroot-val;if(retfalse) return false;bool rightisValidBST(root-right);return leftrightret;} }; 总结 回溯、剪枝真的没有那么神秘再递归里面百分之99都要用到回溯剪枝只是再我们能完成条件之后再考虑优化我们可以尝试以下剪枝。 5. ⼆叉搜索树中第 k ⼩的元素medium
    题意很简单中序遍历k次的值就是第k小的元素 解析 设置两个全局变量retcount那么当countk的时候说明dfs再中序遍历里面已经遇到了k次中序遍历的值得到了第k小的值 1.函数头 void dfs(root); 2.函数体 中序遍历遍历到第k次时找到第k小的值 dfs(root-left); count; if(countk) retroot-val; dfs(root-right); 3.出口条件 知道rootnullptr || ret ! -1 就return只要ret被改变就可以进行剪枝  /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:int ret-1;int _k;int count0;int kthSmallest(TreeNode root, int k) {_kk;dfs(root);return ret;}void dfs(TreeNode* root){if(rootnullptr||ret!-1) return;dfs(root-left);if(count_k) retroot-val;dfs(root-right);} }; 总结 这题真的很简单通过上面的练习就只需要一次中序遍历就可以得到第k小的值。 6. ⼆叉树的所有路径easy 题意很简单将从根节点到叶节点的所有路径放在字符串内进行返回。 解析 虽然这题很简单但只是有这个简单题来突破其他的难题我们需要考虑到很多细节问题 回溯     -      恢复现场 的因果关系是因为有了回溯才出现的恢复现场不能本末倒置了。 只要有递归那么就绝对伴随之回溯只要有深度优先遍历就会存在恢复现场。 为了回溯恢复现场的时候那么就要考虑我们的参数就不能设置为全局变量只需要把他设置为dfs的参数那么就不需要对全局变量进行修改或删除。再每一层的临时变量都是存储当前位置的参数不会被后面递归影响。 再考虑路径值的时候就只需要考虑前序遍历然后添加到字符串内即可。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} };/ class Solution { public:vectorstring ret;vectorstring binaryTreePaths(TreeNode root) {string s;dfs(root,s);return ret;}void dfs(TreeNode* root,string s){if(rootnullptr) return;sto_string(root-val);if(root-leftnullptrroot-rightnullptr) ret.push_back(s);else s-;dfs(root-left,s);dfs(root-right,s);} }; 总结 这里对于回溯和恢复现场真的有很强的表现强烈建议深刻理解以下恢复现场时把参数当作临时变量真的很方便就不需要自己再进行操作。 穷举vs暴搜vs深搜vs回溯vs剪枝
    什么是回溯算法 回溯算法是⼀种经典的递归算法通常⽤于解决组合问题、排列问题和搜索问题等。 回溯算法的基本思想从⼀个初始状态开始按照⼀定的规则向前搜索当搜索到某个状态⽆法前进时回退到前⼀个状态再按照其他的规则搜索。回溯算法在搜索过程中维护⼀个状态树通过遍历状态树来实现对所有可能解的搜索。 回溯算法的核⼼思想“试错”即在搜索过程中不断地做出选择如果选择正确则继续向前搜 索否则回退到上⼀个状态重新做出选择。回溯算法通常⽤于解决具有多个解且每个解都需要搜索才能找到的问题。 回溯算法的模板 void backtrack(vectorint path, vectorint choice, …) {// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i 0; i choices.size(); i) {// 做出选择path.push_back(choices[i]);// 做出当前选择后继续搜索backtrack(path, choices);// 撤销选择path.pop_back();} } 其中 path 表⽰当前已经做出的选择 choices 表⽰当前可以做的选择。在回溯算法中我们需要做出选择然后递归地调⽤回溯函数。如果满⾜结束条件则将当前路径添加到结果集中否则我们需要撤销选择回到上⼀个状态然后继续搜索其他的选择。 回溯算法的时间复杂度通常较⾼因为它需要遍历所有可能的解。但是回溯算法的空间复杂度较低因为它只需要维护⼀个状态树。在实际应⽤中回溯算法通常需要通过剪枝等⽅法进⾏优化以减少搜索的次数从⽽提⾼算法的效率。 7. 全排列medium 题意很简单就是枚举所有可能的排列情况那么废话不多说就是话决策树。 解析 1暴力枚举 两层三层循环还可以枚举如果要排列100层的数那简直不可能只能借助递归来思考。 2递归优化 1.画出决策树越详细越好 2.设计代码 全局变量 int [][] ret int [] path bool [] check 实现剪枝 dfs函数 就需要关系某一个节点在干什么事情 细节问题 回溯 1.干掉path最后一个元素 2.修改check数组 剪枝 递归出口遇到叶子节点就直接添加结果 class Solution { public:vectorvectorint ret;vectorint path;bool check[7];vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);return;}for(int i0;inums.size();i){if(check[i]false){path.push_back(nums[i]);check[i]true;dfs(nums);path.pop_back();check[i]false;}}} }; 总结 最重要的就是画出决策树越细致越好然后通过决策树来观察代码该如何书写。 8. ⼦集medium 题意很简单就是返回数组nums的所有子集。 解析 解法一 1.决策树 2.设计代码 全局变量 vectorvectorint ret; //来记录整体传入的子集     vectorint path;  //设置全局变量来保证传参然后进行手动删除 dfs 细节问题剪枝回溯递归出口 传入nums后要考虑当前位置是否选择分为选择和不选择两种 如果选择那么就是ret.push_back(pathnums[i]) 不选择就是ret.push_back(path) 但是这里要注意的就是不选择要在选择前面这样方便后面选择后的手动删除。再就是dfs传入后就是传入到下一层i1,表示的就是下一层的层数此时回溯到这一层i也不会被改变。 递归出口就是在i的层数在nums.size()的时候就进行最后的添加然后进行返回。 、 class Solution { public:vectorvectorint ret;vectorint path;int check[10];vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int i){if(nums.size()i){ret.push_back(path);return;}//不选dfs(nums,i1);path.push_back(nums[i]);//选dfs(nums,i1);path.pop_back();} }; 解法二 1.画决策树 2.设计代码 全局变量 vectorvectorint ret; //来记录整体传入的子集     vectorint path;  //设置全局变量来保证传参然后进行手动删除 dfs 细节问题回溯 剪枝 递归出口  只用关心每层进去后当前nums下标值的后面的值前面的值不用考虑 例如在1中选21中选3不选2就是在for循环内进行的当进入下一层选2回来这个数组就会删掉2i再次进入下一层选3. class Solution { public:vectorvectorint ret;vectorint path;vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int k){ret.push_back(path);for(int ik;inums.size();i){path.push_back(nums[i]);dfs(nums,i1);path.pop_back();}} }; 总结 我觉得最关键的就是画出决策图然后再进行思考递归出口或者函数体里面的内容像这一题就是跟上一题决策树完全不同思考的方向就完全不同。 总结一下吧~这章对我的进步真的很大希望对你也是