95% 的算法都是基于这 6 种算法思想

写在前面

 

 

因为本次文章篇幅较长，所以为了便利大家查看今日最新职位信息，所以将内容上移至顶部，忘各位大大海涵

 

 

算法思想是解决问题的核心，万丈高楼起于平地，在算法中也是如此，95% 的算法都是基于这 6 种算法思想，结下了介绍一下这 6 种算法思想，帮助你理解及解决各种算法问题。

 

 

1 递归算法

 

 

1.1 算法策略

 

 

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

 

 

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

 

 

优缺点：

 

 

• 优点：实现简单易上手

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

 

 

1.2 适用场景

 

 

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

 

 

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

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

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

 

 

递归的解题策略：

 

 

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

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

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

 

 

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

 

 

• 斐波那契数列

• 汉诺塔问题

• 树的遍历及相关操作

 

 

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 就是用的这样的非递归查找。

 

 

参考：我接触过的前端数据结构与算法

 

 

2 分治算法

 

 

2.1 算法策略

 

 

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

 

 

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

 

 

2.2 适用场景

 

 

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

 

 

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

• 子问题可以很简单的求解

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

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

 

 

分治的解题策略：

 

 

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

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

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

 

 

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

 

 

• 二分查找

• 归并排序

• 快速排序

• 汉诺塔问题

• 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)// 2binarySearch(arr, 5)// -1

 

 

测试成功

 

 

3 贪心算法

 

 

3.1 算法策略

 

 

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

 

 

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

 

 

3.2 适用场景

 

 

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

 

 

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

 

 

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

 

 

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

 

 

例如：求取A到G最短路径：

 

 

根据贪心算法总是选择当前最优选择，所以它首先选择的路径是 AB，然后 BE、EG，所得到的路径总长为 1 + 5 + 4 = 10，然而这并不是最短路径，最短路径为 A->C->G : 2 + 2 = 4，所以说，贪心算法得到得并不一定是最优解。

 

 

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

 

 

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

 

 

• 原问题复杂度过高

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

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

 

 

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

 

 

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

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

 

 

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

 

 

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

 

 

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

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

 

 

3.3 经典案例：活动选择问题

 

 

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

 

 

• 最小生成树算法

• 单源最短路径的 Dijkstra 算法

• Huffman 压缩编码

• 背包问题

• 活动选择问题等

 

 

其中活动选择问题是最简单的，这里详细介绍这个。

 

 

活动选择问题是《算法导论》上的例子，也是一个非常经典的问题。有 n 个活动（a1,a2,…,an）需要使用同一个资源（例如教室），资源在某个时刻只能供一个活动使用。每个活动 AI 都有一个开始时间 si 和结束时间 fi 。一旦被选择后，活动 ai 就占据半开时间区间 [si,fi) 。如果 [si,fi) 和 [sj,fj) 互不重叠，ai 和 aj 两个活动就可以被安排在这一天。

 

 

该问题就是要安排这些活动，使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。

 

 

共有 7 个活动，它们在 18 个小时内需要占用的时间如上图，如何选择活动，能让这间教室利用率最高喃（能够举行更多的活动）？

 

 

贪心算法对这种问题的解决很简单的，它开始时刻开始选择，每次选择开始时间与与已选择活动不冲突的，结束时间又比较靠前的活动，这样会让剩下的时间区间更长。

 

 

• 首先 a1 活动的结束时间最早，选择 a1 活动

• a1 结束后，a2 有时间冲突，不可选择，a3、a4 都可选择，但 a4 结束时间最早，选择 a4

• 依次选择时间没有冲突的，又结束时间最早的活动

 

 

最终选择活动为 a1，a4，a5，a7。为最优解。

 

 

4 回溯算法

 

 

4.1 算法策略

 

 

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

 

 

4.2 适用场景

 

 

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

 

 

4.3 使用回溯算法的经典案例

 

 

• 深度优先搜索

• 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 匹配结束。

 

 

5 动态规划

 

 

5.1 算法策略

 

 

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

 

 

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

 

 

5.2 适用场景

 

 

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

 

 

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

 

 

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

 

 

• 定义子问题

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

• 识别并求解出边界条件

 

 

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

 

 

• 爬楼梯问题：假设你正在爬楼梯。需要 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)

 

 

6 枚举算法

 

 

6.1 算法策略

 

 

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

 

 

6.2 解题思路

 

 

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

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

 

 

7 刷题

 

 

7.1 爬楼梯问题

 

 

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

 

 

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

 

注意： 给定 n 是一个正整数。

 

 

示例 1：

 

 

输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

 

 

示例 2：

 

 

输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

 

 

解法：动态规划

 

 

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

 

 

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

 

 

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

 

 

• 定义子问题

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

• 识别并求解出边界条件

 

 

第一步：定义子问题

 

 

如果用 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)

 

 

7.2 使用最小花费爬楼梯

 

 

数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。

 

 

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

 

 

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

 

 

示例 1:

 

 

输入: cost = [10, 15, 20]输出: 15解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

 

 

示例 2:

 

 

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]输出: 6解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

 

 

注意：

 

 

• cost 的长度将会在 [2, 1000] 。

• 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999] 。

 

 

解法：动态规划

 

 

本题注意理解题意：

 

 

• 第 i 级台阶是第 i-1 级台阶的阶梯顶部。

• 踏上第 i 级台阶花费 cost[i] ，直接迈一大步跨过而不踏上去则不用花费。

• 楼梯顶部在数组之外，如果数组长度为 len，那么楼顶就在下标为 len

 

 

第一步：定义子问题

 

 

踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

 

 

• 最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost[i]

• 最后迈 1 步踏上第 i 级台阶：dp[i-2] + cost[i]

 

 

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

 

 

所以踏上第 i 级台阶的最小花费为：

 

 

dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

 

 

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

 

 

// 第 0 级 cost[0] 种方案 dp[0] = cost[0]// 第 1 级，有两种情况// 1：分别踏上第0级与第1级台阶，花费cost[0] + cost[1]// 2：直接从地面开始迈两步直接踏上第1级台阶，花费cost[1]dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]

 

 

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

 

 

let minCostClimbingStairs = function(cost) {    cost.push(0)    let dp = [], n = cost.length    dp[0] = cost[0]    dp[1] = cost[1]    for(let i = 2; i < n; i++){        dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]    }    return dp[n-1]}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(n)

 

 

优化：

 

 

let minCostClimbingStairs = function(cost) {    let n = cost.length,        n1 = cost[0],        n2 = cost[1]     for(let i = 2;i < n;i++){        let tmp = n2        n2 = Math.min(n1,n2)+cost[i]        n1 = tmp    }    return Math.min(n1,n2)};

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(1)

 

 

更多解答

 

 

7.3 最大子序和

 

 

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 

 

示例:

 

 

输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 

 

进阶:

 

 

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

 

 

第一步：定义子问题

 

 

动态规划是将整个数组归纳考虑，假设我们已经知道了以第 i-1 个数结尾的连续子数组的最大和 dp[i-1]，显然以第i个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums[i]，要么就是 nums[i] 单独成一组，也就是 nums[i] ，在这两个数中我们取最大值

 

 

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

 

 

dp[n] = Math.max(dp[n−1]+nums[n], nums[n])

 

 

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

 

 

dp[0]=nums[0]

 

 

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

 

 

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 nums[i]，因此不用把整个 dp 数组保存下来，只需设置一个 pre 保存 dp[i-1] 就好了。

 

 

代码实现（优化）：

 

 

let maxSubArray = function(nums) {    let max = nums[0], pre = 0    for(const num of nums) {        if(pre > 0) {            pre += num        } else {            pre = num        }        max = Math.max(max, pre)    }    return max}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(1)

 

 

7.4 买卖股票的最佳时机

 

 

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

 

 

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

 

 

注意：你不能在买入股票前卖出股票。

 

 

示例 1:

 

 

输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

 

 

示例 2:

 

 

输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

 

 

解法：动态规划

 

 

第一步：定义子问题

 

 

动态规划是将整个数组归纳考虑，假设我们已经知道了 i-1 个股票的最大利润为 dp[i-1]，显然 i 个连续股票的最大利润为 dp[i-1] ，要么就是就是 prices[i] - minprice （ minprice 为前 i-1 支股票的最小值 ），在这两个数中我们取最大值

 

 

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

 

 

dp[i] = Math.max(dp[i−1], prices[i] - minprice)

 

 

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

 

 

dp[0]=0

 

 

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

 

 

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 prices[i]，因此不用把整个 dp 数组保存下来，只需设置一个 max 保存 dp[i-1] 就好了。

 

 

代码实现（优化）：

 

 

let maxProfit = function(prices) {    let max = 0, minprice = prices[0]    for(let i = 1; i < prices.length; i++) {        minprice = Math.min(prices[i], minprice)        max = Math.max(max, prices[i] - minprice)    }    return max}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(1)

 

 

7.5 回文子串

 

 

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

 

 

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

 

 

示例 1：

 

 

输入："abc"输出：3解释：三个回文子串: "a", "b", "c"

 

 

示例 2：

 

 

输入："aaa"输出：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

 

 

提示：

 

 

• 输入的字符串长度不会超过 1000 。

 

 

解法一：暴力法

 

 

let countSubstrings = function(s) {  let count = 0  for (let i = 0; i < s.length; i++) {    for (let j = i; j < s.length; j++) {      if (isPalindrome(s.substring(i, j + 1))) {        count++      }    }  }  return count}let isPalindrome = function(s) {  let i = 0, j = s.length - 1  while (i < j) {    if (s[i] != s[j]) return false    i++    j--  }  return true}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n^3^)

• 空间复杂度：O(1)

 

 

解法二：动态规划

 

 

一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。

 

 

我们怎么去描述子问题呢？

 

 

显然，一个子串由两端的 i 、j 指针确定，就是描述子问题的变量，子串 s[i...j] （ dp[i][j] ） 是否是回文串，就是子问题。

 

 

我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。

 

 

    j    a  a  b  ai a ✅  a    ✅    b       ✅  a          ✅

 

 

注意： i<=j ，只需用半张表，竖向扫描

 

 

所以：

 

 

i === j：dp[i][j]=truej - i == 1 && s[i] == s[j]：dp[i][j] = truej - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]：dp[i][j] = true

 

 

即：

 

 

s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true

 

 

否则为 false

 

 

代码实现：

 

 

let countSubstrings = function(s) {  const len = s.length  let count = 0  const dp = new Array(len)  for (let i = 0; i < len; i++) {    dp[i] = new Array(len).fill(false)  }  for (let j = 0; j < len; j++) {    for (let i = 0; i <= j; i++) {      if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {        dp[i][j] = true        count++      } else {        dp[i][j] = false      }    }  }  return count}

 

 

代码实现（优化）：

 

 

把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将 dp 定义为一维数组即可

 

 

let countSubstrings = function(s) {  const len = s.length  let count = 0  const dp = new Array(len)  for (let j = 0; j < len; j++) {    for (let i = 0; i <= j; i++) {      if (s[i] === s[j] && (j - i <= 1 || dp[i + 1])) {        dp[i] = true        count++      } else {        dp[i] = false      }    }  }  return count;}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n^2^)

• 空间复杂度：O(n)

 

 

更多解答

 

 

7.6 最长回文子串

 

 

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

 

 

示例 1：

 

 

输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。

 

 

示例 2：

 

 

输入: "cbbd"输出: "bb"

 

 

解法：动态规划

 

 

第 1 步：定义状态

 

 

dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j] 。

 

 

第 2 步：思考状态转移方程

 

 

对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串

 

 

dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

 

 

第 3 步：初始状态：

 

 

dp[i][i] = true // 单个字符是回文串if(s[i] === s[i+1]) dp[i][i+1] = true // 连续两个相同字符是回文串

 

 

代码实现：

 

 

const longestPalindrome = (s) => {  if (s.length < 2) return s  // res: 最长回文子串  let res = s[0], dp = []  for (let i = 0; i < s.length; i++) {    dp[i][i] = true  }  for (let j = 1; j < s.length; j++) {    for (let i = 0; i < j; i++) {      if (j - i === 1 && s[i] === s[j]) {        dp[i][j] = true      } else if (s[i] === s[j] && dp[i + 1][j - 1]) {        dp[i][j] = true      }         // 获取当前最长回文子串      if (dp[i][j] && j - i + 1 > res.length) {        res = s.substring(i, j + 1)      }    }  }  return res}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n^2^)

• 空间复杂度：O(n^2^)

 

 

7.7 最小路径和

 

 

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

 

 

说明：每次只能向下或者向右移动一步。

 

 

示例 1：

 

 

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。

 

 

示例 2：

 

 

输入：grid = [[1,2,3],[4,5,6]]输出：12

 

 

提示：

 

 

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 200

• 0 <= grid[i][j] <= 100

 

 

1、DP方程 当前项最小路径和 = 当前项值 + 上项或左项中的最小值 grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )

 

 

2、边界处理 grid的第一行与第一列 分别没有上项与左项 故单独处理计算起项最小路径和 计算第一行：

 

 

for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

 

 

计算第一列：

 

 

for(let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

 

 

3、代码实现

 

 

var minPathSum = function(grid) {    let row = grid.length, col = grid[0].length    // calc boundary    for(let i = 1; i < row; i++)        // calc first col        grid[i][0] += grid[i - 1][0]    for(let j = 1; j < col; j++)        // calc first row        grid[0][j] += grid[0][j - 1]    for(let i = 1; i < row; i++)        for(let j = 1; j < col; j++)            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])        return grid[row - 1][col - 1]};

 

 

7.8 买卖股票的最佳时机 II

 

 

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

 

 

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

 

 

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

 

示例 1:

 

 

输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

 

 

示例 2:

 

 

输入: [1,2,3,4,5]输出: 4解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

 

 

示例 3:

 

 

输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

 

 

提示：

 

 

• 1 <= prices.length <= 3 * 10 ^ 4

• 0 <= prices[i] <= 10 ^ 4

 

 

解法一：峰底买入，峰顶卖出

 

 

如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下

 

 

解法二：贪心算法

 

 

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

 

 

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

 

 

对应于该题，第一天买入，第二天卖出，…，第 i 天买入，第 i+1 天卖出，如果 i 天买入第 i+1 天卖出有利润则买入，否则不买

 

 

第 i-1 天买入第 i 天卖出获利 prices[i+1]-prices[i] ，我们仅仅需要将 prices[i+1]-prices[i] 的所有正值加起来就是可获取的最大利益

 

 

代码实现：

 

 

let maxProfit = function(prices) {    let profit = 0    for (let i = 0; i < prices.length - 1; i++) {        if (prices[i + 1] > prices[i]) {            profit += prices[i + 1] - prices[i]        }    }    return profit}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(1)

 

 

7.9 分发饼干

 

 

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 g~i~ ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s~j~。如果 s~j~ >= g~i~ ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

 

 

注意：

 

 

你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

 

 

示例 1:

 

 

输入: [1,2,3], [1,1]输出: 1解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

 

 

示例 2:

 

 

输入: [1,2], [1,2,3]输出: 2解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2.

 

 

解法：贪心算法

 

 

const findContentChildren = (g, s) => {    if (!g.length || !s.length) return 0        g.sort((a, b) => a - b)    s.sort((a, b) => a - b)        let gi = 0, si = 0    while (gi < g.length && si < s.length) {        if (g[gi] <= s[si++]) gi++    }    return gi}

 

 

7.10 分割数组为连续子序列

 

 

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

 

 

如果可以完成上述分割，则返回 true ；否则，返回 false 。

 

 

示例 1：

 

 

输入: [1,2,3,3,4,5]输出: True解释:你可以分割出这样两个连续子序列 : 1, 2, 33, 4, 5

 

 

示例 2：

 

 

输入: [1,2,3,3,4,4,5,5]输出: True解释:你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 53, 4, 5

 

 

示例 3：

 

 

输入: [1,2,3,4,4,5]输出: False

 

 

提示：

 

 

• 输入的数组长度范围为 [1, 10000]

 

 

解法：贪心算法

 

 

从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为3），剔除之后，依次往后遍历：

 

 

• 判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接

• 如果不可以，则判断以当前元素开始能否构成连续子序列（长度为3），可以的话，则剔除连续子序列

• 否则，返回 false

 

 

const isPossible = function(nums) {    let max = nums[nums.length - 1]    // arr：存储原数组中数字每个数字出现的次数    // tail：存储以数字num结尾的且符合题意的连续子序列个数    let arr = new Array(max + 2).fill(0),         tail = new Array(max + 2).fill(0)    for(let num of nums) {        arr[num] ++    }    for(let num of nums) {        if(arr[num] === 0) continue        else if(tail[num-1] > 0){            tail[num-1]--            tail[num]++        }else if(arr[num+1] > 0 && arr[num+2] > 0){            arr[num+1]--            arr[num+2]--            tail[num+2]++        } else {            return false        }        arr[num]--    }    return true}

 

 

复杂度分析：

 

 

• 时间复杂度：O(n)

• 空间复杂度：O(n)

 

 

7.11 全排列问题

 

 

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

 

 

示例:

 

 

输入: [1,2,3]输出:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]

 

 

解法：回溯算法

 

 

本题是回溯算法的经典应用场景

 

 

1. 算法策略

 

 

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

 

 

2. 适用场景

 

 

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

 

 

3. 代码实现

 

 

我们可以写一下，数组 [1, 2, 3] 的全排列有：

 

 

• 先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；

• 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；

• 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

 

 

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

 

 

这显然是一个 递归 结构；

 

 

• 递归的终止条件是：一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；

• used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

 

 

let permute = function(nums) {    // 使用一个数组保存所有可能的全排列    let res = []    if (nums.length === 0) {        return res    }    let used = {}, path = []    dfs(nums, nums.length, 0, path, used, res)    return res}let dfs = function(nums, len, depth, path, used, res) {    // 所有数都填完了    if (depth === len) {        res.push([...path])        return    }    for (let i = 0; i < len; i++) {        if (!used[i]) {            // 动态维护数组            path.push(nums[i])            used[i] = true            // 继续递归填下一个数            dfs(nums, len, depth + 1, path, used, res)            // 撤销操作            used[i] = false            path.pop()        }          }}

 

 

4. 复杂度分析

 

 

• 时间复杂度：O(n∗n!)，其中 n 为序列的长度这是一个排列组合，每层的排列组合数为：A^m^ ~n~=n!/(n−m)! ，故而所有的排列有 ：A^1^ ~n~ + A^2^ ~n~ + … + A^n-1^ ~n~ = n!/(n−1)! + n!/(n−2)! + … + n! = n! * (1/(n−1)! + 1/(n−2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1^) < 2 * n!并且每个内部结点循环 n 次，故非叶子结点的时间复杂度为 O(n∗n!)

• 空间复杂度：O(n)

 

 

7.12 括号生成

 

 

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

 

示例：

 

 

输入：n = 3输出：[       "((()))",       "(()())",       "(())()",       "()(())",       "()()()"     ]

 

 

解答：回溯算法（深度优先遍历）

 

 

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

 

 

对应于本题，我们可以每次试探增加 ( 或 ) ，注意：

 

 

• 加入 ( 的条件是，当前是否还有 ( 可以选择

• 加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

 

 

代码实现：

 

 

const generateParenthesis = (n) => {    const res = []    const dfs = (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)    return res}

 

 

复杂度分析（来源leetcode官方题解）：

 

 

本文转载自三分钟学前端