递归算法

算法策略

递归算法是一种直接或者间接调用自身函数或者方法的算法。

递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。

优缺点：

优点：实现简单易上手

缺点：递归算法对常用的算法如普通循环等，运行效率较低；并且在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归太深，容易发生栈溢出。

适用场景

递归算法一般用于解决三类问题：

数据的定义是按递归定义的。（斐波那契数列）

问题解法按递归算法实现。（回溯）

数据的结构形式是按递归定义的。（树的遍历，图的搜索）

递归的解题策略：

第一步：明确你这个函数的输入输出，先不管函数里面的代码什么，而是要先明白，你这个函数的输入是什么，输出为何什么，功能是什么，要完成什么样的一件事。

第二步：寻找递归结束条件，我们需要找出什么时候递归结束，之后直接把结果返回

第三步：明确递归关系式，怎么通过各种递归调用来组合解决当前问题

使用递归算法求解的一些经典问题

斐波那契数列

汉诺塔问题

树的遍历及相关操作

DOM树为例

下面以以 DOM 树为例，实现一个 document.getElementById 功能

由于DOM是一棵树，而树的定义本身就是用的递归定义，所以用递归的方法处理树，会非常地简单自然。

第一步：明确你这个函数的输入输出

从 DOM 树根节点一层层往下递归，判断当前节点的 id 是否是我们要寻找的 id='d-cal'

输入：DOM 树根节点 document ，我们要寻找的 id='d-cal'

输出：返回满足 id='sisteran' 的子结点

function getElementById(node, id){}

第二步：寻找递归结束条件

从document开始往下找，对所有子结点递归查找他们的子结点，一层一层地往下查找：

如果当前结点的 id 符合查找条件，则返回当前结点

如果已经到了叶子结点了还没有找到，则返回 null

function getElementById(node, id){
    // 当前结点不存在，已经到了叶子结点了还没有找到，返回 null
    if(!node) return null
    // 当前结点的 id 符合查找条件，返回当前结点
    if(node.id === id) return node
}

第三步：明确递归关系式

当前结点的 id 不符合查找条件，递归查找它的每一个子结点

function getElementById(node, id){
    // 当前结点不存在，已经到了叶子结点了还没有找到，返回 null
    if(!node) return null
    // 当前结点的 id 符合查找条件，返回当前结点
    if(node.id === id) return node
    // 前结点的 id 不符合查找条件，继续查找它的每一个子结点
    for(var i = 0; i < node.childNodes.length; i++){
        // 递归查找它的每一个子结点
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}

就这样，我们的一个 document.getElementById 功能已经实现了：

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");

使用递归的优点是代码简单易懂，缺点是效率比不上非递归的实现。Chrome浏览器的查DOM是使用非递归实现。非递归要怎么实现呢？如下代码：

function getByElementId(node, id){
    //遍历所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}

还是依次遍历所有的 DOM 结点，只是这一次改成一个 while 循环，函数 nextElement 负责找到下一个结点。所以关键在于这个 nextElement 如何实现非递归查找结点功能：

// 深度遍历
function nextElement(node){
    // 先判断是否有子结点
    if(node.children.length) {
        // 有则返回第一个子结点
        return node.children[0];
    }
    // 再判断是否有相邻结点
    if(node.nextElementSibling){
        // 有则返回它的下一个相邻结点
        return node.nextElementSibling;
    }
    // 否则，往上返回它的父结点的下一个相邻元素，相当于上面递归实现里面的for循环的i加1
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}

在控制台里面运行这段代码，同样也可以正确地输出结果。不管是非递归还是递归，它们都是深度优先遍历。实际上 getElementById 浏览器是用的一个哈希 map 存储的，根据 id 直接映射到 DOM 结点，而 getElementsByClassName 就是用的这样的非递归查找。

分治算法

算法策略

在计算机科学中，分治算法是一个很重要的算法，快速排序、归并排序等都是基于分治策略进行实现的，所以，建议理解掌握它。

分治，顾名思义，就是 分而治之 ，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为阿子问题解的合并。

适用场景

当出现满足以下条件的问题，可以尝试只用分治策略进行求解：

原始问题可以分成多个相似的子问题

子问题可以很简单的求解

原始问题的解是子问题解的合并

各个子问题是相互独立的，不包含相同的子问题

分治的解题策略：

第一步：分解，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

第二步：解决，解决各个子问题

第三步：合并，将各个子问题的解合并为原问题的解

使用分治法求解的一些经典问题

二分查找

归并排序

快速排序

汉诺塔问题

React 时间分片

二分查找

也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。

第一步：分解

每次猜拳都把上一次的结果分出大的一组和小的一组，两组相互独立

选择数组中的中间数

function binarySearch(items, item) {
    // low、mid、high将数组分成两组
    var low = 0,
        high = items.length - 1,
        mid = Math.floor((low+high)/2),
        elem = items[mid]
    // ...
}

第二步：解决子问题

查找数与中间数对比

比中间数低，则去中间数左边的子数组中寻找；

比中间数高，则去中间数右边的子数组中寻找；

相等则返回查找成功

while(low <= high) {
 if(elem < item) { // 比中间数高
  low = mid + 1
 } else if(elem > item) { // 比中间数低
  high = mid - 1
 } else { // 相等
     return mid
 }
}

第三步：合并

function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

最后，二分法只能应用于数组有序的情况，如果数组无序，二分查找就不能起作用了

function binarySearch(items, item) {
    // 快排
    quickSort(items)
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

// 测试
var arr = [2,3,1,4]
binarySearch(arr, 3)
// 2

binarySearch(arr, 5)
// -1

贪心算法

算法策略

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。

适用场景

在日常生活中，我们使用到贪心算法的时候还是挺多的，例如：

从100章面值不等的钞票中，抽出 10 张，怎样才能获得最多的价值？

我们只需要每次都选择剩下的钞票中最大的面值，最后一定拿到的就是最优解，这就是使用的贪心算法，并且最后得到了整体最优解。

但是，我们任然需要明确的是，期望通过局部的最优选择获得整体的最优选择，仅仅是期望而已，也可能最终得到的结果并不一定不能是整体最优解。

那么一般在什么时候可以尝试选择使用贪心算法喃？

当满足一下条件时，可以使用：

原问题复杂度过高

求全局最优解的数学模型难以建立或计算量过大

没有太大必要一定要求出全局最优解，“比较优”就可以

如果使用贪心算法求最优解，可以按照以下 步骤求解 ：

首先，我们需要明确什么是最优解（期望）

然后，把问题分成多个步骤，每一步都需要满足：

可行性：每一步都满足问题的约束

局部最优：每一步都做出一个局部最优的选择

不可取消：选择一旦做出，在后面遇到任何情况都不可取消

最后，叠加所有步骤的最优解，就是全局最优解

经典案例：活动选择问题

使用贪心算法求解的经典问题有：

最小生成树算法

单源最短路径的 Dijkstra 算法

Huffman 压缩编码

背包问题

活动选择问题等

回溯算法

算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

使用回溯算法的经典案例

深度优先搜索

0-1背包问题

正则表达式匹配

八皇后

数独

全排列

这里以正则表达式匹配为例，介绍一下

正则表达式匹配

var string = "abbc"
var regex = /ab{1,3}c/
console.log( string.match(regex) )
// \\["abbc", index: 0, input: "abbc", groups: undefined\\]

它的匹配过程：

在第 5 步匹配失败，此时 b{1,3} 已经匹配到了两个 b 正在尝试第三个 b ，结果发现接下来是 c 。此时就需要回溯到上一步， b{1,3} 匹配完毕（匹配到了 bb ），然后再匹配 c ，匹配到了 c 匹配结束。

动态规划

算法策略

动态规划也是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

所以，动态规划适用于子问题重叠的情况，即不同的子问题具有公共的子子问题，在这种情况下，分治策略会做出很多不必要的工作，它会反复求解那些公共子子问题，而动态规划会对每个子子问题求解一次，然后保存在表格中，如果遇到一致的问题，从表格中获取既可，所以它无需求解每一个子子问题，避免了大量的不必要操作。

适用场景

动态规划适用于求解最优解问题，比如，从面额不定的100个硬币中任意选取多个凑成10元，求怎样选取硬币才可以使最后选取的硬币数最少又刚好凑够了10元。这就是一个典型的动态规划问题。它可以分成一个个子问题（每次选取硬币），每个子问题又有公共的子子问题（选取硬币），子问题之间相互关联（已选取的硬币总金额不能超过10元），边界条件就是最终选取的硬币总金额为 10 元。

针对上例，也许你也可以说，我们可以使用回溯算法，不断的去试探，但回溯算法是使用与求解广度的解（满足要求的解），如果是用回溯算法，我们需要尝试去找所有满足条件的解，然后找到最优解，时间复杂度为 O(2^n^) ，这性能是相当差的。大多数适用于动态规划的问题，都可以使用回溯算法，只是使用回溯算法的时间复杂度比较高而已。

最后，总结一下，我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

定义子问题

实现需要反复执行解决的子子问题部分

识别并求解出边界条件

使用动态规划求解的一些经典问题

爬楼梯问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

背包问题：给出一些资源（有总量及价值），给一个背包（有总容量），往背包里装资源，目标是在背包不超过总容量的情况下，装入更多的价值

硬币找零：给出面额不定的一定数量的零钱，以及需要找零的钱数，找出有多少种找零方案

图的全源最短路径：一个图中包含 u、v 顶点，找出从顶点 u 到顶点 v 的最短路径

最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变剩下元素的顺序实现）

这里以最长公共子序列为例。

爬楼梯问题

这里以动态规划经典问题爬楼梯问题为例，介绍求解动态规划问题的步骤。

第一步：定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步：实现需要反复执行解决的子子问题部分

dp[n] = dp[n−1] + dp[n−2]

第三步：识别并求解出边界条件

// 第 0 级 1 种方案
dp[0]=1
// 第 1 级也是 1 种方案

六种算法思想


dp[1]=1

最后一步：把尾码翻译成代码，处理一些边界情况

let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

优化空间复杂度：

let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

空间复杂度：O(1)

枚举算法

算法策略

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。

解题思路

确定枚举对象、枚举范围和判定条件。

逐一列举可能的解，验证每个解是否是问题的解。

总结

算法是编程的"里子"，不管你是前端还是后端，作为一名计算机工程师，具备一定的算法能力，是一种基本要求。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

{{userData.name}}已认证

编程六种算法思想

递归算法

算法策略

适用场景

使用递归算法求解的一些经典问题

DOM树为例

分治算法

算法策略

适用场景

使用分治法求解的一些经典问题

二分查找

贪心算法

算法策略

适用场景

经典案例：活动选择问题

回溯算法

算法策略

适用场景

使用回溯算法的经典案例

正则表达式匹配

动态规划

算法策略

适用场景

使用动态规划求解的一些经典问题

爬楼梯问题

枚举算法

算法策略

解题思路

总结

JavaScript中几种数组去重的方式

公共DNS服务介绍