# 前言

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

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

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

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

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

年轻时候去大厂的目标，是为了避免，【你得顿悟，是别人的基本功】

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

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

# 数据结构

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

常用数据结构
- 数组，字符串
- 链表
- 栈
- 队列
- 树
高级数据结构
- 图
- 前缀树
- 线段树
- 树状数组
- 主席树

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

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

普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。

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

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

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

掌握好这些数据结构是基础，绝大部分的算法面试题都得靠它们来帮忙，因此，一定要花功夫勤练题目来深入理解它们。

# 排序算法

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

当时我梳理得是常见的 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 专题

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

Wikipedia 定义：它既是一种数学优化的方法，同时也是编程的方法。

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

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

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

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

解题思路，三大步骤👇