当前位置 博文首页 > 李dayday：「算法与数据结构」我的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 定义：它既是一种数学优化的方法，同时也是编程的方法。
?
当然了，看完这段话，我们肯定对它不了解的，我们可以翻译一下，首先它可以算是一种优化的手段，优化一些重复子问题的操作，将很多重叠子问题通过编程的方式来解决，比如「记忆划搜索」。又比如，如果一个原问题，可以拆分成很多子问题，它们之间没有任何后续性，当前的决策对后续没有影响的话，每个子问题的最优解，就可以组合成原问题的最优解了。
当然了，对于动态规划每个人理解是不同的，对于应用到具体的场景中，需要我们都去用多维度的状态去表述它的含义，这里也就是状态转移方程的含义所在。
嗯，那么动态规划解决了什么问题呢，很显然，对于重复性问题来说，它可以很好的解决，那么从某个维度上来看，它可以优化一个算法的时间复杂度，也就是通常意义上的，拿空间来换取时间的操作。
「动态规划解题步骤」：这个应该就是实际落地的操作，需要我们去通过大量的题目来完成，具体我们需要怎么做呢？
解题思路，三大步骤????
「状态定义」
「列出状态转移方程」
「初始化状态」
「算法与数据结构」一张脑图带你看动态规划算法之美强烈推荐这篇问题，里面讲的很清楚了。
「如何高效率刷dp专题」：首先，你得找到对应的dp专题，这里的话，我帮你准备好了，接下来我说一下我是怎么刷leetcode上面的题目的。
一般而言，刷完中等的leetcode上的dp专题，基本上可以满足要求了。那么对于中等的dp题目，很多时候，我是写不吃来的，那我应该如何去做呢？
首先，我先看题解，把它的状态转移方程写下来，仔细的品味一下，它这么定义，解决了我之前的什么难点，为啥我是没有想到的。
然后，看完之后，尝试按照这个题解思路，我自己能不能单独实现呢？
如果不能的话，就照着它的代码，写一遍，多看看状态转移方程是如何写的，把这个题目收藏起来。
等到下次，或者是隔天，再来看一遍题目，然后看看能不能单独完成，如果不能，第三天再这么操作。
还有，我个人建议，刷dp的话，最好从易到难，这样子自己也会有信心，也不会再去畏惧它。
以下是我收集的部分题目，希望对你们有帮助。
爬楼梯
打家劫舍
使用最小花费爬楼梯
连续数列
三步问题
打家劫舍 II
最佳买卖股票时机含冷冻期
打家劫舍 III
不同路径
不同路径 II
最长上升子序列
买卖股票的最佳时机 III
买卖股票的最佳时机 IV
青蛙过河
单词拆分 II
最大子矩阵
这部分也是尤其重要的，那么重点学习深度优先搜索算法（简称为 DFS）和广度优先搜索算法（简称为 BFS）。
我翻了翻我的博客，恰好有一篇类似的问题，大家可以看看**「算法与数据结构」DFS和BFS算法之美**。
不过，我看了一下，我当时写得时候，有点粗糙，很多基本的概念都没有讲明白，所以可能适合一些对这部分有基础的小伙伴。
在这里推荐一个有趣的题目：
穿过迷宫的最少移动次数
如果你也遇到过迷宫类似的问题，就可以考虑搜索算法了，从我个人的角度来说，它的思路其实就是模拟人的思路，每次走到一个路口的时候，我可以走哪里，我之前走过的路，怎么确保，接下来是不能走的，这里需要在编程的角度，如何去实现呢？
这里说一说我的经验，对于刚刚提到的题目而言，我盲猜使用BFS，题目做多了，自然就会有心得，对于BFS和DFS而言，做了两个类似的题目，会发现，原来搜索算法也是有迹可循，也是存在某些套路的。
给些建议：
一开始可能做的时候，抓不到头脑，有思路，但是代码很难写清楚，那么如何去做呢？「看题解」，了解别人的写法是很不错的，可以多个对比，看看哪一份题解代码是你目前可以理解的，然后抄下来，看一遍。
最普通的办法就是：先画图，看看思维上跟实际代码需要做哪些改变，如何去优化这个过程。最后结合别人代码，一定不要直接copy，不去思考为什么这么写，不然后期发现，是没有多大效果的，一定要多结合自己的理解。
嗯，不会就看题解，多思考为什么这么写！！！
写到这里的时候，已经凌晨1点了，算法与数据结构这个方向太大了，一篇文章不可能写得完，我更希望这篇文章对你，有那么一点点的帮助，对我，或你都些许有所帮助，那么它得存在就有那么一点点意义。
以下是我刷的题集，需者自取，公众号：「前端UpUp」，关注它，找我领pdf文档也可以。
这个专题想进阶，就刷我下面提供的题目吧????
二叉树的最大深度
二叉树的最小深度
朋友圈
找到最终的安全状态
矩阵中的最长递增路径
扫雷游戏
单词接龙
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/
简单
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/
简单
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/
简单
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/
简单
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/
如果你觉得这篇内容对你挺有有帮助的话：
点赞支持下吧，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
关注公众号「前端UpUp」，联系作者???? 「DayDay2021」 ，我们一起学习一起进步。
觉得不错的话，也可以阅读TianTian近期梳理的文章（感谢掘友的鼓励与支持????????????）：
