前端程序员学好算法系列(九)递归回溯算法

回溯算法主要应用于树形问题,我们先从一个简单的算法入手

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)

};
(0)

相关推荐

  • 终于学完国内算法第一人10年经验总结的数据结构与算法详解文档

    相信想进一线大厂的程序员是非常多的,也是程序员一直以来的梦,不仅仅是因为薪资比较高,更多的是因为大厂比较锻炼人,将来的发展空间也是非常大的! 近年来,在面试大厂中,算法的比重是越来越高了,像BATJ ...

  • ​LeetCode刷题实战283:移动零

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 七大排序算法总结

    以下所有动图均来源于一像素博客园 以下代码均使用C 编写 完整代码请到这里下载 稳定排序算法:冒泡排序.插入排序.归并排序 时间复杂度不受数据影响:选择排序.归并排序.堆排序 时间复杂度基本小于n2: ...

  • 前端笔试题——数组去重(保姆级手撕)

    引言: 对于传统的前端工程师来说,更多的只是把服务端响应的数据渲染到页面上. 随着前端的不断进化,算法对我们而言也日渐重要,大公司为了优中选优,经常也会用算法题去筛选更优秀的人才. 算法,或许在工作中 ...

  • LeetCode 热题 HOT 100

    LeetCode 热题 HOT 100

  • ​LeetCode刷题实战152:乘积最大子数组

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 面试被问到 HashMap 底层原理?我有点慌.

    快速入门 存储:put 方法 put(key,value) 查询:get 方法 get(key) java 代码如下 import java.util.HashMap;import java.util ...

  • 前端程序员学好算法系列(六)队列

    利用队列我们可以解决很多问题,js数组也可以实现队列,队列的思想为先近先出,js可以用 push和 shift() 很容易的实现一个队列 给你一个二叉树,请你返回其按 层序遍历 得到的节点值. (即逐 ...

  • 前端程序员学好算法系列(五)栈

    前端程序员学好算法系列(五)栈

  • 前端程序员学好算法系列(四)链表

    24. 两两交换链表中的节点 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表. 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换. 示例: 给定 1->2->3-&g ...

  • 程序员应知系列 - CPU执行原理

    任何计算机系统的真正复杂性都存在于处理器中,但是您知道它是如何工作的吗? 我是说它到底是怎么运作的?您编写的代码如何变成可以完成某些工作的东西? 当您知道CPU如何工作时,就知道不是魔术了 - 而是& ...

  • 程序员应知系列CPU执行原理(当处理器将地址放置在地址总线上时将选择一个特定的存储位置)

    (当处理器将地址放置在地址总线上时将选择一个特定的存储位置) https://m.toutiao.com/is/eyC48ar/ 任何计算机系统的真正复杂性都存在于处理器中,但是您知道它是如何工作的吗 ...

  • 如今前端程序员还有前途吗?

    目前,前端程序员仍然是IT行业比较火的技术之一,在现在或将来,只要我们在互联网上使用前端程序员,就一定是一个很有前途的行业.因此,对于现在的前端程序员是否有前途,对这个问题的回答是肯定的. 特别在当今 ...

  • 93年的程序员在外企朝九晚五,年薪60万,却想辞职去考公务员

    如今有很多员工在进入社会工作以后,其实对于自己的工作并不是很满意,都希望自己能够在行业中获得较好的发展,但是却看到自己跟同学跟同事的差距变得越来越大,而且生活和工作没有了热乐趣,大家就不想再去完成,梦 ...

  • 诚之和:怎么让前端程序员没有后端也能完成项目

    这篇文章主要讲解了"怎么让前端程序员没有后端也能完成项目",文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习"怎么让前端程序员没 ...

  • 前端程序员的进阶

    前言 如何成为一名优秀的前端工程师 要有自己的前端知识体系 逐步完善自己的三大能力,首先是编程能力,其次是工程能力,最后是架构能力 在工作中完善自己的领域知识,如教育类,电商类等等 构建自己的知识体系 ...