前言
最近好多事情,最近前端分享会也如期而至,有幸这次分享会,正好周末有时间,做个总结吧。
这次想分享的就是算法与数据结构,刷了一段时间题目,逛了逛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的话,最好从易到难,这样子自己也会有信心,也不会再去畏惧它。
进阶题目汇总
以下是我收集的部分题目,希望对你们有帮助。
简单
中等
困难
搜索算法
这部分也是尤其重要的,那么重点学习深度优先搜索算法(简称为 DFS)和广度优先搜索算法(简称为 BFS)。
我翻了翻我的博客,恰好有一篇类似的问题,大家可以看看**「算法与数据结构」DFS和BFS算法之美**。
不过,我看了一下,我当时写得时候,有点粗糙,很多基本的概念都没有讲明白,所以可能适合一些对这部分有基础的小伙伴。
在这里推荐一个有趣的题目:
如果你也遇到过迷宫类似的问题,就可以考虑搜索算法了,从我个人的角度来说,它的思路其实就是模拟人的思路,每次走到一个路口的时候,我可以走哪里,我之前走过的路,怎么确保,接下来是不能走的,这里需要在编程的角度,如何去实现呢?
这里说一说我的经验,对于刚刚提到的题目而言,我盲猜使用BFS,题目做多了,自然就会有心得,对于BFS和DFS而言,做了两个类似的题目,会发现,原来搜索算法也是有迹可循,也是存在某些套路的。
给些建议:
一开始可能做的时候,抓不到头脑,有思路,但是代码很难写清楚,那么如何去做呢? 看题解,了解别人的写法是很不错的,可以多个对比,看看哪一份题解代码是你目前可以理解的,然后抄下来,看一遍。
最普通的办法就是:先画图,看看思维上跟实际代码需要做哪些改变,如何去优化这个过程。最后结合别人代码,一定不要直接copy,不去思考为什么这么写,不然后期发现,是没有多大效果的,一定要多结合自己的理解。
嗯,不会就看题解,多思考为什么这么写!!!
写到这里的时候,已经凌晨1点了,算法与数据结构这个方向太大了,一篇文章不可能写得完,我更希望这篇文章对你,有那么一点点的帮助,对我,或你都些许有所帮助,那么它得存在就有那么一点点意义。
以下是我刷的题集,需者自取,公众号:前端UpUp,关注它,找我领pdf文档也可以。
进阶题目汇总
这个专题想进阶,就刷我下面提供的题目吧👇
DFS
BFS
题目汇总
我之前刷题历程是根据这套题来的,我觉得里面题目梯度还是质量都是很不错的。
拿到这个pdf有段时间了,所以不清楚具体作者是谁,有侵权的话,可删。
数组&链表
简单
中等
Map & Set
简单
中等
堆栈&队列
简单
中等
二分查找
简单
中等
困难
递归
简单
中等
哈希表
简单
中等
困难
二叉树
简单
中等
困难
二叉搜索树
简单
中等
困难
图
中等
堆和排序
简单
困难
DFS
简单
中等
困难
BFS
简单
中等
Trie树
简单
中等
困难
分治算法
简单
中等
回溯算法
简单
中等
困难
贪心算法
简单
中等
动态规划
简单
中等
困难
❤️ 感谢大家
如果你觉得这篇内容对你挺有有帮助的话:
- 点赞支持下吧,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
- 关注公众号前端UpUp,联系作者👉 DayDay2021 ,我们一起学习一起进步。
- 觉得不错的话,也可以阅读TianTian近期梳理的文章(感谢掘友的鼓励与支持🌹🌹🌹):
- 「算法与数据结构」一张脑图带你看动态规划算法之美(370+👍)
- 「算法与数据结构」Trie树之美(200+👍)
- 「算法与数据结构」分治算法之美(190+👍)
- 「算法与数据结构」DFS和BFS算法之美(240+👍)
- 「算法与数据结构」梳理6大排序算法(220+👍)
- 「算法与数据结构」带你看哈希算法之美(210+👍)
- 「算法与数据结构」带你看回溯算法之美(190+👍)
今天的文章「算法与数据结构」你可能需要的一份前端算法总结分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/14227.html