回溯算法主要应用于树形问题,我们先从一个简单的算法入手 17. 电话号码的字母组合 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例: 输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 解题:
1.我们建立一个map的数据结构,把键盘数字代表的字母一一传入map中; map.get(digits[i])为当前传入的第i个字符代表的字母集合 2. _generate() 我们传入两个变量 i 当前选择的第几个字母,str 默认传入'' /** * @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] ] 解题: /** * @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 = 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() 每次我们加入的数据在递归结果前需要删除掉 /** * @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) };
|
|