「算法与数据结构」你可能需要的一份前端算法总结

前言

最近好多事情，最近前端分享会也如期而至，有幸这次分享会，正好周末有时间，做个总结吧。

这次想分享的就是算法与数据结构，刷了一段时间题目，逛了逛LeetCode，看了很多关于这个方面的文章，有所感悟，准备做个记录吧。

当你想花时间去了解学习一件对你来说，很苦难的事情的时候，我们需要明确目标，学习它的意义，它有什么用，对你有哪方面帮助。

升职加薪必备，对以后成长有所帮助，嗯，加薪，加薪，加薪。

那么问题来了，为什么要进大厂呢⬇️

嗯，闲聊就止步于此，接下来开始吧～

站在巨人肩膀上，学起来就很轻松了， 这里我是参考网上的算法刷题路线，可以参考一下～

公众号前端UpUp，回复算法，即可获取脑图，以及文末的题目汇总pdf。

接下来，我们就根据这个脑图来梳理一遍吧~

数据结构

数据结构可以说是算法的基石，如果没有扎实的数据结构基础，想要把算法学好甚至融会贯通是非常困难的，而优秀的算法又往往取决于你采用哪种数据结构。学好这个专题也是很有必要的，那么我们可以稍微的做个分类。

• 常用数据结构

  • 数组，字符串
  • 链表
  • 栈
  • 队列
  • 树

• 高级数据结构

  • 图
  • 前缀树
  • 线段树
  • 树状数组
  • 主席树

那么显然，最常见的数据结构一定是需要掌握的，对于高级的数据结构而言，如果你有时间，对它有所热爱的话，可以深入了解，比如这个主席树在解决一些问题 的时候，算法复杂度是log级别的，某些场景下很有帮助。

这里想提及的就是树。它的结构很显然是很直观的，树当然有很多的性质，这里也列举不完，比如面试中常考的树：

对于它而言的话，我们需要到哪些程度呢？

对于常见树的遍历，从树的前序遍历，到中序遍历，后续遍历，以至于层次遍历，掌握好这四种遍历的递归写法和非递归写法是非常重要的，接下来需要懂得分析各种写法的时间复杂度和空间复杂度。

面试准备阶段，把树这个结构花时间去准备的话，对于你理解递归还是很有帮助的，同时也能帮助你学习一些图论的知识，更加准确的说，树是面试考察的热门考点，尤其是二叉树！

排序算法

这应该是面试最常考，最核心的算法。如果你能把排序算法理解的很透彻的话，接下来的其他算法也是一样的旁敲侧击。

当时我梳理得是常见的6个排序算法：

• 冒泡排序
• 计数排序
• 快速排序
• 归并排序
• 插入排序
• 选择排序

在此之前，我也写过一篇排序算法的文章，个人觉得言简意赅，可以看看「算法与数据结构」梳理6大排序算法

有时候，面试官喜欢会问冒泡排序和插入排序，基本上这些都是考察你的基础知识，并且看看你能不能快速地写出没有bug的代码。

又比如，当面试官问你归并排序、快速排序和拓扑排序等的时候，这个时候考察的是你平时对算法得积累，所以有必要做个总结。

我们拿归并排序来举例子，我们应该如何表达清楚呢？首先，我们应该把这个它的思路说清楚：

归并排序的核心思想就是分治，它将一个复杂的问题分成两个或者多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。

当你向面试官理清楚这个思路时，面试官心里就有底了，他会想，嘿，这个小伙子不错！那你接下来都有底气了！

有了思想，那么实现起来就不难了:

贴一份之前的代码：

const merge = (left, right) => { // 合并数组

    let result = []
    // 使用shift()方法偷个懒,删除第一个元素,并且返回该值
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift())
        } else {
            result.push(right.shift())
        }
    }
    while (left.length) {
        result.push(left.shift())
    }

    while (right.length) {
        result.push(right.shift())
    }
    return result
}

let mergeSort = function (arr) {
    if (arr.length <= 1)
        return arr
    let mid = Math.floor(arr.length / 2)
    // 拆分数组
    let left = arr.slice(0, mid),
        right = arr.slice(mid);
    let mergeLeftArray = mergeSort(left),
        mergeRightArray = mergeSort(right)
    return merge(mergeLeftArray, mergeRightArray)
}

// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(mergeSort(arr))

对于这部分的算法而言，可以围绕从解题思路-->>实现过程-->>代码实现。 基本上以这三步来实现的话，掌握常见的排序算法完成是没有问题的。

那么这部分就暂时梳理到这里吧。

动态规划

动态规划难，可以说是很多面试者也是我最怕的部分，尤其是面试的时候，怕面试官考这个算法了。遇到没有做过的题目，这个时候，能否写出状态转移方程是十分重要的。接下来我们聊一聊这个专题吧。

首先，强烈推荐我之前分析这个专题如何准备的： 「算法与数据结构」一张脑图带你看动态规划算法之美

如果从点赞角度来看，可以说，是我写算法以来，得到大家肯定最多的一次了，可以看看，不过这里也会涵盖部分。

如何学动态规划，从哪里入手，应该这么去做，这么去刷题，肯定是很多初学者一开始就会遇到的问题。

• 概念
• 动态规划解决了什么问题
• 动态规划解题的步骤
• 如何高效率刷dp专题

首先，你得了解动态规划是什么，它的思想是什么，定义又是啥。这里引入维基百科对它的定义：

当然了，看完这段话，我们肯定对它不了解的，我们可以翻译一下，首先它可以算是一种优化的手段，优化一些重复子问题的操作，将很多重叠子问题通过编程的方式来解决，比如记忆划搜索。 又比如，如果一个原问题，可以拆分成很多子问题，它们之间没有任何后续性，当前的决策对后续没有影响的话，每个子问题的最优解，就可以组合成原问题的最优解了。

当然了，对于动态规划每个人理解是不同的，对于应用到具体的场景中，需要我们都去用多维度的状态去表述它的含义，这里也就是状态转移方程的含义所在。

嗯，那么动态规划解决了什么问题呢，很显然，对于重复性问题来说，它可以很好的解决，那么从某个维度上来看，它可以优化一个算法的时间复杂度，也就是通常意义上的，拿空间来换取时间的操作。

动态规划解题步骤： 这个应该就是实际落地的操作，需要我们去通过大量的题目来完成，具体我们需要怎么做呢？

解题思路，三大步骤?

1. 状态定义
2. 列出状态转移方程
3. 初始化状态

「算法与数据结构」一张脑图带你看动态规划算法之美强烈推荐这篇问题，里面讲的很清楚了。

如何高效率刷dp专题：首先，你得找到对应的dp专题，这里的话，我帮你准备好了，接下来我说一下我是怎么刷leetcode上面的题目的。

一般而言，刷完中等的leetcode上的dp专题，基本上可以满足要求了。那么对于中等的dp题目，很多时候，我是写不吃来的，那我应该如何去做呢？

• 首先，我先看题解，把它的状态转移方程写下来，仔细的品味一下，它这么定义，解决了我之前的什么难点，为啥我是没有想到的。
• 然后，看完之后，尝试按照这个题解思路，我自己能不能单独实现呢？
• 如果不能的话，就照着它的代码，写一遍，多看看状态转移方程是如何写的，把这个题目收藏起来。
• 等到下次，或者是隔天，再来看一遍题目，然后看看能不能单独完成，如果不能，第三天再这么操作。

还有，我个人建议，刷dp的话，最好从易到难，这样子自己也会有信心，也不会再去畏惧它。

进阶题目汇总

以下是我收集的部分题目，希望对你们有帮助。

简单

• 爬楼梯
• 打家劫舍
• 使用最小花费爬楼梯
• 连续数列
• 三步问题

中等

• 打家劫舍 II
• 最佳买卖股票时机含冷冻期
• 打家劫舍 III
• 不同路径
• 不同路径 II
• 最长上升子序列

困难

• 买卖股票的最佳时机 III
• 买卖股票的最佳时机 IV
• 青蛙过河
• 单词拆分 II
• 最大子矩阵

搜索算法

这部分也是尤其重要的，那么重点学习深度优先搜索算法（简称为 DFS）和广度优先搜索算法（简称为 BFS）。

我翻了翻我的博客，恰好有一篇类似的问题，大家可以看看**「算法与数据结构」DFS和BFS算法之美**。

不过，我看了一下，我当时写得时候，有点粗糙，很多基本的概念都没有讲明白，所以可能适合一些对这部分有基础的小伙伴。

在这里推荐一个有趣的题目：

穿过迷宫的最少移动次数

如果你也遇到过迷宫类似的问题，就可以考虑搜索算法了，从我个人的角度来说，它的思路其实就是模拟人的思路，每次走到一个路口的时候，我可以走哪里，我之前走过的路，怎么确保，接下来是不能走的，这里需要在编程的角度，如何去实现呢？

这里说一说我的经验，对于刚刚提到的题目而言，我盲猜使用BFS，题目做多了，自然就会有心得，对于BFS和DFS而言，做了两个类似的题目，会发现，原来搜索算法也是有迹可循，也是存在某些套路的。

给些建议：

一开始可能做的时候，抓不到头脑，有思路，但是代码很难写清楚，那么如何去做呢？ 看题解，了解别人的写法是很不错的，可以多个对比，看看哪一份题解代码是你目前可以理解的，然后抄下来，看一遍。

最普通的办法就是：先画图，看看思维上跟实际代码需要做哪些改变，如何去优化这个过程。最后结合别人代码，一定不要直接copy，不去思考为什么这么写，不然后期发现，是没有多大效果的，一定要多结合自己的理解。

嗯，不会就看题解，多思考为什么这么写！！！

写到这里的时候，已经凌晨1点了，算法与数据结构这个方向太大了，一篇文章不可能写得完，我更希望这篇文章对你，有那么一点点的帮助，对我，或你都些许有所帮助，那么它得存在就有那么一点点意义。

以下是我刷的题集，需者自取，公众号：前端UpUp，关注它，找我领pdf文档也可以。

进阶题目汇总

这个专题想进阶，就刷我下面提供的题目吧?

DFS

• 二叉树的最大深度
• 二叉树的最小深度
• 朋友圈
• 找到最终的安全状态
• 矩阵中的最长递增路径
• 扫雷游戏
• 单词接龙

BFS

• N叉树的层序遍历
• 二叉树的层序遍历
• 最小高度树
• 扫雷游戏

题目汇总

我之前刷题历程是根据这套题来的，我觉得里面题目梯度还是质量都是很不错的。

拿到这个pdf有段时间了，所以不清楚具体作者是谁，有侵权的话，可删。

数组&链表

简单

• leetcode-cn.com/problems/re…

• leetcode-cn.com/problems/ro…

• leetcode-cn.com/problems/me…

• leetcode-cn.com/problems/me…

中等

• leetcode-cn.com/problems/sw…

• leetcode-cn.com/problems/3s…

Map & Set

简单

• leetcode-cn.com/problems/va…

中等

• leetcode-cn.com/problems/gr…

堆栈&队列

简单

• leetcode-cn.com/problems/re…

• leetcode-cn.com/problems/re…

中等

• leetcode.com/problems/la…

• leetcode.com/problems/tr…

二分查找

简单

• leetcode-cn.com/problems/ar…

中等

• leetcode-cn.com/problems/po…

困难

• leetcode-cn.com/problems/du…

递归

简单

• leetcode-cn.com/problems/ma…

• leetcode-cn.com/problems/sy…

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/bi…

• leetcode-cn.com/problems/ra…

中等

• leetcode-cn.com/problems/lo…

哈希表

简单

• leetcode-cn.com/problems/tw…

• leetcode-cn.com/problems/va…

中等

• leetcode-cn.com/problems/lo…

• leetcode-cn.com/problems/to…

困难

• leetcode-cn.com/problems/nu…

二叉树

简单

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/lo…

中等

• leetcode-cn.com/problems/sy…

• leetcode-cn.com/problems/bi…

• leetcode-cn.com/problems/bi…

困难

• leetcode-cn.com/problems/se…

二叉搜索树

简单

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/lo…

中等

• leetcode-cn.com/problems/va…

• leetcode-cn.com/problems/ra…

• leetcode-cn.com/problems/co…

困难

• leetcode-cn.com/problems/co…

图

中等

• leetcode.com/problems/nu…

• leetcode-cn.com/problems/co…

堆和排序

简单

• leetcode-cn.com/problems/kt…

困难

• leetcode-cn.com/problems/fi…

DFS

简单

• leetcode-cn.com/problems/ma…

• leetcode-cn.com/problems/mi…

中等

• leetcode-cn.com/problems/fr…

• leetcode-cn.com/problems/fi…

困难

• leetcode-cn.com/problems/lo…

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/wo…

BFS

简单

• leetcode-cn.com/problems/n-…

• leetcode-cn.com/problems/bi…

• leetcode.com/problems/bi…

中等

• leetcode.com/problems/bi…

• leetcode-cn.com/problems/mi…

• leetcode-cn.com/problems/mi…

Trie树

简单

• leetcode-cn.com/problems/lo…

中等

• leetcode-cn.com/problems/im…

• leetcode-cn.com/problems/ad…

困难

• leetcode-cn.com/problems/wo…

分治算法

简单

• leetcode-cn.com/problems/ma…

中等

• leetcode-cn.com/problems/ma…

• leetcode-cn.com/problems/se…

回溯算法

简单

• leetcode-cn.com/problems/le…

中等

• leetcode-cn.com/problems/su…

• leetcode-cn.com/problems/pe…

• leetcode-cn.com/problems/co…

困难

• leetcode-cn.com/problems/n-…

贪心算法

简单

• leetcode-cn.com/problems/as…

中等

• leetcode-cn.com/problems/be…

动态规划

简单

• leetcode-cn.com/problems/cl…

• leetcode.com/problems/ho…

中等

• leetcode-cn.com/problems/be…

• leetcode.com/problems/ho…

• leetcode.com/problems/ho…

• leetcode.com/problems/un…

• leetcode.com/problems/un…

困难

• leetcode-cn.com/problems/be…

• leetcode-cn.com/problems/be…

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：

1. 点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
2. 关注公众号前端UpUp，联系作者? DayDay2021 ，我们一起学习一起进步。
3. 觉得不错的话，也可以阅读TianTian近期梳理的文章（感谢掘友的鼓励与支持???）：
   • 「算法与数据结构」一张脑图带你看动态规划算法之美（370+?）
   • 「算法与数据结构」Trie树之美（200+?）
   • 「算法与数据结构」分治算法之美（190+?）
   • 「算法与数据结构」DFS和BFS算法之美(240+?)
   • 「算法与数据结构」梳理6大排序算法(220+?)
   • 「算法与数据结构」带你看哈希算法之美(210+?)
   • 「算法与数据结构」带你看回溯算法之美(190+?)