「算法与数据结构」我的2020前端算法小结

前言

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

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

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

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

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

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

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

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

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

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

数据结构

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

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

那么显然，最常见的数据结构一定是需要掌握的，对于高级的数据结构而言，如果你有时间，对它有所热爱的话，可以深入了解，比如这个「主席树」在解决一些问题 的时候，算法复杂度是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 定义：它既是一种数学优化的方法，同时也是编程的方法。 ❞

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

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

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

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

解题思路，三大步骤?

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

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

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

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

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

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

进阶题目汇总

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

简单

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

中等

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

困难

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

搜索算法

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

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

穿过迷宫的最少移动次数

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

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

给些建议：

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

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

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

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

进阶题目汇总

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

DFS

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

BFS

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

题目汇总

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

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

数组&链表

简单

• https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
• https://leetcode-cn.com/problems/rotate-array/
• https://leetcode-cn.com/problems/merge-two-sorted-lists/
• https://leetcode-cn.com/problems/merge-sorted-array/

中等

• https://leetcode-cn.com/problems/swap-nodes-in-pairs/
• https://leetcode-cn.com/problems/3sum/

Map & Set

简单

• https://leetcode-cn.com/problems/valid-anagram/

中等

• https://leetcode-cn.com/problems/group-anagrams/

堆栈&队列

简单

• https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
• https://leetcode-cn.com/problems/remove-outermost-parentheses/

中等

• https://leetcode.com/problems/largest-rectangle-in-histogram/
• https://leetcode.com/problems/trapping-rain-water/

二分查找

简单

• https://leetcode-cn.com/problems/arranging-coins/

中等

• https://leetcode-cn.com/problems/powx-n/

困难

• https://leetcode-cn.com/problems/dungeon-game/

递归

简单

• https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
• https://leetcode-cn.com/problems/symmetric-tree/
• https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
• https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
• https://leetcode-cn.com/problems/binary-tree-paths/
• https://leetcode-cn.com/problems/range-sum-of-bst/

中等

• https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

哈希表

简单

• https://leetcode-cn.com/problems/two-sum/
• https://leetcode-cn.com/problems/valid-anagram/

中等

• https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
• https://leetcode-cn.com/problems/top-k-frequent-words

困难

• https://leetcode-cn.com/problems/number-of-atoms/

二叉树

简单

• https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
• https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

中等

• https://leetcode-cn.com/problems/symmetric-tree/
• https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
• https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

困难

• https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

二叉搜索树

简单

• https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
• https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search

中等

• https://leetcode-cn.com/problems/validate-binary-search-tree/
• https://leetcode-cn.com/problems/range-sum-of-bst/
• https://leetcode-cn.com/problems/contains-duplicate-iii/

困难

• https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

图

中等

• https://leetcode.com/problems/number-of-islands/
• https://leetcode-cn.com/problems/course-schedule-ii

堆和排序

简单

• https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

困难

• https://leetcode-cn.com/problems/find-median-from-data-stream/

DFS

简单

• https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
• https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

中等

• https://leetcode-cn.com/problems/friend-circles/
• https://leetcode-cn.com/problems/find-eventual-safe-states/

困难

• https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
• https://leetcode-cn.com/problems/minesweeper/
• https://leetcode-cn.com/problems/word-ladder/

BFS

简单

• https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
• https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
• https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

中等

• https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
• https://leetcode-cn.com/problems/minesweeper/
• https://leetcode-cn.com/problems/minimum-height-trees/

Trie树

简单

• https://leetcode-cn.com/problems/longest-word-in-dictionary/

中等

• https://leetcode-cn.com/problems/implement-trie-prefix-tree/
• https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/

困难

• https://leetcode-cn.com/problems/word-search-ii/

分治算法

简单

• https://leetcode-cn.com/problems/majority-element/

中等

• https://leetcode-cn.com/problems/maximum-subarray/
• https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

回溯算法

简单

• https://leetcode-cn.com/problems/letter-case-permutation/

中等

• https://leetcode-cn.com/problems/subsets/
• https://leetcode-cn.com/problems/permutations/
• https://leetcode-cn.com/problems/combinations/

困难

• https://leetcode-cn.com/problems/n-queens/

贪心算法

简单

• https://leetcode-cn.com/problems/assign-cookies/

中等

• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

动态规划

简单

• https://leetcode-cn.com/problems/climbing-stairs/
• https://leetcode.com/problems/house-robber/

中等

• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
• https://leetcode.com/problems/house-robber-ii/
• https://leetcode.com/problems/house-robber-iii/
• https://leetcode.com/problems/unique-paths/
• https://leetcode.com/problems/unique-paths-ii/

困难

• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
• https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/