前端程序员学好算法系列(九)递归回溯算法
回溯算法主要应用于树形问题,我们先从一个简单的算法入手
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解题:
digits是数字字符串
s(digits) 是digits所能代表的字符串
s(digits[0..n-1])
= letter(digits[0]) +s(digits[1...n-1])
=letter(digits[0]) + letter(digits[1]) +s(digits[2...n-1])
1.我们建立一个map的数据结构,把键盘数字代表的字母一一传入map中; map.get(digits[i])为当前传入的第i个字符代表的字母集合
2. _generate() 我们传入两个变量 i 当前选择的第几个字母,str 默认传入''
3. 当i的值等于digits.length是我们获得了一个结果push到result中
4.循环当前的数字代表的字母 ,一一传入_generate(i+1,str+tmp[r]); 遍历其他结果
/** * @param {string} digits * @return {string[]} */ var letterCombinations = function(digits) { if(!digits){ return []; } var len = digits.length; var map = new Map(); map.set('1',''); map.set('2','abc'); map.set('3','def'); map.set('4','ghi'); map.set('5','jkl'); map.set('6','mno'); map.set('7','pqrs'); map.set('8','tuv'); map.set('9','wxyz'); var result = []; function _generate(i,str){ if(i == len){ result.push(str); return; } var tmp = map.get(digits[i]); for(var r = 0;r<tmp.length;r++){ _generate(i+1,str+tmp[r]); } } _generate(0,''); return result; };
46. 全排列
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解题:
1.回溯标准解题模板res 存放结果的数组,tmpPath为传入的数组,当 tmpPath.length == n是我们得到一个满足条件的解,
2. !tmpPath.includes(nums[i]) 来过滤防止数组tmpPath存在重复的值
3. tmpPath.push(nums[i]); 数组中加入值后,递归完成后,相应的值需要从数组中减去,tmpPath.pop()
4.数组为引用类型,防止取值错误我们取 tmpPath.slice()继续遍历
5.每次遍历index+1 进行下次遍历
/** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { let n = nums.length; let res = []; let tmpPath = []; let backtrack = (index,tmpPath) => { if(tmpPath.length == n){ res.push(tmpPath); return; } for(let i = 0;i < n;i++){ if(!tmpPath.includes(nums[i])){ tmpPath.push(nums[i]); backtrack(index+1,tmpPath.slice()); tmpPath.pop(); } } } backtrack(0,tmpPath); return res; }
77. 组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
1.求解n,k,当前已经找到的组合储存在res中,需要从start位置处开始搜索
2.could.length == k我们获得了一个满足条件的解
3. could.push(i) could.pop() 每次我们加入的数据在递归结果前需要删除掉
4.每次递归循环时从i的下一位开始找
/** * @param {number} n * @param {number} k * @return {number[][]} */ var combine = function(n, k) { var res = []; var could = []; if(k==0){ return [[]] } function dfs(start,n,res,could){ if(could.length == k){ res.push(could.slice(0)); return; } for(var i = start ; i<n+1;i++){ could.push(i); dfs(i+1,n,res,could); could.pop() } return res; } return dfs(1,n,res,could) };