上海专业做网站的公司有哪些设计师门户网站源码

上海专业做网站的公司有哪些,设计师门户网站源码,哪里有建设,网站内容和备案不一一.递归算法1.什么是递归递归是一种在计算机科学和数学中广泛使用的重要概念#xff0c;它指的是一个函数或算法直接或间接地调用自身来解决问题的方法。在二叉树的前中后序遍历中,我们也经常使用递归实现2.核心思想递归将复杂问题分解为更小的、相似的子问题#xff0c;通过…一.递归算法1.什么是递归递归是一种在计算机科学和数学中广泛使用的重要概念它指的是一个函数或算法直接或间接地调用自身来解决问题的方法。在二叉树的前中后序遍历中,我们也经常使用递归实现2.核心思想递归将复杂问题分解为更小的、相似的子问题通过解决这些子问题最终解决原始问题。递归包含两个关键部分3.递归的特点(1)把问题转化为规模缩小的同类问题的子问题只关心当前这次传参怎么处理。(2)有明确的递归结束的条件base case(3)有决策过程4.如何实现递归(1)明确当前函数要干嘛(2).怎么调用递归,如何传入参数(3).递归什么时候结束(必须要有的条件)(4).递归中如何处理当前参数5.经典递归问题(1)数字阶乘int factorial_recursive(int n) { //递归结束条件 if (n 0 || n 1) { return 1; } else { //递归处理逻辑 return n * factorial_recursive(n - 1); } }(2)斐波拉契数列int fibonacci_recursive_basic(int n) { //递归结束条件 if (n 0) return 0; if (n 1||n2) return 1; //递归处理逻辑 return fibonacci_recursive_basic(n - 1) fibonacci_recursive_basic(n - 2); }从上面两个递归经典实现我们可以发现,递归结束条件和递归处理逻辑在递归算法中是必不可少的尤其是结束条件,由于递归算法会重复调用函数,占用栈区内存,如果没有结束条件,那么就会出现无限递归的情况,当栈区空间被占满时,程序就会崩溃所以结束条件在递归中的非常非常重要的6.递归的优缺点:(1)优点:代码简洁、优雅逻辑清晰适用于处理递归定义的数据结构如树、图更容易实现分治算法(2)缺点:可能产生大量函数调用占用栈空间(递归深度过大也会导致程序崩溃)可能存在重复计算如朴素斐波那契递归调试可能比较困难二.回溯算法说完了递归,就不得不提到递归的一个使用--回溯算法了1.什么是回溯算法:回溯算法是一种通过试错来寻找问题解决方案的算法。它采用深度优先搜索的策略在搜索过程中逐步构建解决方案当发现当前路径不可能得到正确解时会回溯退回到上一步尝试其他可能性。而由于其退回到上一步的特点,非常适合使用递归来实现2.核心特点:系统性搜索尝试所有可能的解决方案递归实现通常用递归实现每层递归做一个选择剪枝优化在发现当前路径不可能成功时提前终止状态恢复回溯时需要撤销当前选择恢复状态3.回溯算法的使用:在二叉树中,常用于按需要寻找二叉树的路径力扣257.二叉树的所有路径给你一个二叉树的根节点root按任意顺序返回所有从根节点到叶子节点的路径。思路:每次遍历到叶子节点,将该路径拼接完成后,删除路径数组中最后一个元素,相当于回到其父节点,进行另一条路径的搜索代码实现:class Solution { public: //回溯算法的实现 void func(TreeNode* root,vectorintpath,vectorstringans){ //每次将当前节点放入数组中 path.push_back(root-val); //判断是不是叶子节点,如果是就进行处理 if(root-leftnullptrroot-rightnullptr){ //拼接路径 string s to_string(path[0]); for(int i 1;ipath.size();i){ s-; sto_string(path[i]); } //将其放入结果数组中 ans.push_back(s); } //递归调用,若左(右)子树存在,将其传入参数 if(root-left){ func(root-left,path,ans); //!!核心!! //回溯算法,每次拼接路径完成后,将最后一个叶子节点删除 //相当于退回到该叶子节点的父节点进行另一条路径的搜索 path.pop_back(); } if(root-right){ func(root-right,path,ans); path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorintpath; vectorstringans; func(root,path,ans); return ans; } };力扣112.路径总和给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和targetSum。如果存在返回true否则返回false。代码实现:class Solution { public: void func(TreeNode* root,vectorintpath,vectorintans){ //递归结束条件 if(rootnullptr)return; //递归处理逻辑 path.push_back(root-val); //如果是叶子节点,就计算路径总和 if(root-leftnullptrroot-rightnullptr){ int sum 0; for(int i 0;ipath.size();i){ sumpath[i]; } ans.push_back(sum); } //递归传入其左节点或右节点 if(root-left){ func(root-left,path,ans); //和上题一样,回溯算法的使用 path.pop_back(); } if(root-right){ func(root-right,path,ans); path.pop_back(); } } bool hasPathSum(TreeNode* root, int targetSum) { vectorintpath; vectorintans; func(root,path,ans); //将所有路径总和相加,判断是否和目标值相等 for(int i 0;ians.size();i){ if(ans[i]targetSum){ return true; } } return false; } };像力扣129也是属于使用回溯算法记录每条路径,再进行相应的操作,这里就不一一列举了4.回溯算法优缺点:优点:(1)系统性能穷举所有可能的解决方案(2)通用性强适用于多种类型的问题(3)容易理解和实现框架清晰逻辑简单(4)能保证找到解如果解存在一定能找到缺点:(1)时间复杂度高通常是指数级或阶乘级复杂度(2)可能效率低下对于大规模问题不适用(3)需要剪枝优化否则效率极低三.总结:1. 递归与回溯的关系递归是基础回溯算法通常用递归实现递归提供了回溯所需的返回上一层的能力回溯是应用回溯是递归的一种特定应用场景专注于试错-返回的搜索策略2.核心区别特性递归回溯目的解决可分解为子问题的问题通过试错搜索所有可能的解实现函数调用自身通常基于递归实现状态管理不需要显式状态恢复需要显式状态恢复撤销选择应用场景阶乘、斐波那契、树遍历等排列组合、N皇后、路径搜索等3. 关键要点递归三要素明确的递归结束条件将问题分解为子问题递归调用解决子问题回溯四要素路径已经做出的选择选择列表当前可以做的选择结束条件达到决策树底层无法再做选择撤销选择回溯的核心回到上一步优化技巧递归优化记忆化、尾递归优化、迭代改写回溯优化剪枝、提前终止无效搜索、状态压缩