- Notifications
You must be signed in to change notification settings - Fork646
Description
上周发了篇文章，关于一名 95 后女程序员（4 年前端开发），对现状的担忧与对未来的焦虑担忧，文章一经发出，后台就收到很多反馈，大部分的人都表示认同：
因此，我决定把自己的每日进阶记录下来，有时可能 2-3 天一起，每日内容不多，如果你不清楚怎么做，就和我一起吧，如果你有规划，也可以关注「三分钟学前端」，添加我的微信pzijun_com，将你的每日进阶记录发送到群群里，我们一起督促学习
回溯算法
什么是回溯算法问题？
回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。它就是不断的尝试，直到拿到解。因此它类似于一种暴力穷举的算法，此类问题一般都很少考虑时间复杂度问题
它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解，或得到所有满足要求的解。因此它常采用深度优先遍历（DFS）求解
我们最常遇到的问题，例如：
- 全排列问题
- 括号生成问题
- 组合总和问题
- 树的深度遍历问题
全排列问题
给定一个没有重复 数字的序列，返回其所有可能的全排列。
输入:[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
它的核心思路就是类似一个多叉树的形式，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
letpermute=function(nums){// 使用一个数组保存所有可能的全排列letres=[]if(nums.length===0){returnres}letused={},path=[]dfs(nums,nums.length,0,path,used,res)returnres}letdfs=function(nums,len,depth,path,used,res){// 所有数都填完了if(depth===len){res.push([...path])return}for(leti=0;i<len;i++){if(!used[i]){// 动态维护数组path.push(nums[i])used[i]=true// 继续递归填下一个数dfs(nums,len,depth+1,path,used,res)// 撤销操作used[i]=falsepath.pop()}}}
括号生成问题
数字n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的 括号组合。
示例：
输入：n=3输出：["((()))","(()())","(())()","()(())","()()()"]
对应于本题，最开始是''，我们可以每次试探增加( 或) ，注意：
- 加入
(的条件是，当前是否还有(可以选择 - 加入
)的时候，受到(的限制，如果已选择的结果里的(小于等于已选择里的)时，此时是不能选择)的，例如如果当前是()，继续选择)就是())，是不合法的
代码实现：
constgenerateParenthesis=(n)=>{constres=[]constdfs=(path,left,right)=>{// 肯定不合法，提前结束if(left>n||left<right)return// 到达结束条件if(left+right===2*n){res.push(path)return}// 选择dfs(path+'(',left+1,right)dfs(path+')',left,right+1)}dfs('',0,0)returnres}
组合总和问题
给你一个 无重复元素 的整数数组candidates 和一个目标整数target ，找出candidates 中可以使数字和为目标数target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以无限制重复被选取 。- 如果至少一个数字的被选数量不同，则两种组合是不同的。
输入:candidates=[2,3,5],target=8输出:[[2,2,2,2],[2,3,3],[3,5]]
对应于本题，从candidates 选择数，每个数可以选择多次，使用index 记录当前选到第几个数，不可向前选择，防止重复，count 为当前满足条件的index 位的数最多可选count 次，由0 ... count 次往后递归
paths：已选数sum：已选数和index：当前选到第几个数
varcombinationSum=function(candidates,target){letres=[],map=newMap()letdfs=function(paths,sum,index){if(sum>target||index>candidates.length)returnif(target===sum){res.push(paths)return}// 计算当前数可选的倍数letcount=Math.floor((target-sum)/candidates[index])// 选择当前数for(leti=0;i<=count;i++){dfs(newArray(i).fill(candidates[index]).concat(paths),sum+i*candidates[index],index+1)}}dfs([],0,0)returnres};
优化：
varcombinationSum=function(candidates,target){letres=[],map=newMap()letdfs=function(paths,sum,index){if(sum>target||index>candidates.length)returnif(target===sum){res.push(paths)return}dfs(paths,sum,index+1)if(target-sum>=candidates[index]){dfs([...paths,candidates[index]],sum+candidates[index],index)}}dfs([],0,0)returnres};