大厂相信很多人都是很想进去的 , 基本上大厂第一关的笔试题都是考算法 , 算法确实很重要 , 虽然都是写业务层的业务逻辑 , 同样一个问题 , 你不会的需要执行时间是3秒 , 人家只需要0.1秒 , 你说老板要谁 , 可以这么说 , 都是写for循环 , 你写的没人要 ,人家写的就价格不菲 , 差距就在这算法上 , 而好的算法势必是选对了数据结构 ,所谓专业的人干专业的事情 , 数组就是用来进行查找比较好 , 你非用它来进行增删操作 , 当然也可以 , 只不过执行时间上的差距就一目了然了 !

我3月份面试了华为的 , 由于一点都不了解里边的情况 , 直接一封邮件过来 , 我还以为立马就得去做 , 然后直接上了 , 一考懵逼了 ,是真的不会啊 !
接下来开这个专栏来记录我的算法之旅

这一篇文章主要介绍我们的数据结构需要掌握哪些 以及掌握到那种程度 , 以及对应LeetCode上的经典例题

常用数据结构

数组、字符串、链表、栈、队列、双端队列、树

数组

优点

构建一个数组非常简单

能让我们在O(1)的时间里根据数组的下标(index)查询某个元素

缺点

构建时必须分配一段连续空间

查询某个元素是否存在时需要遍历整个数组 , 耗费O(n)的时间(其中 , n是元素的个数)

删除和添加某个元素时 , 同样需要耗费O(n)的时间

适用场景 : 适用于查询

leetcode 242题 有效的字母异位词

链表

单链表 : 链表中的每个元素实际上是一个单独的对象 , 而所有对象都通过每个元素中的引用字段连接在一起

双链表 : 与单链表不同的是 , 双链表中的每个节点中都含有 两个引用字段

优点

灵活的分配内存空间

能在O(1)时间内删除或者添加元素

缺点

查询元素需要O(n)时间

适用场景 : 适用于增加和删除

leetcode 25题 K个一组翻转链表

栈

特点

后进先出

适用场景 : 只关心上一次的操作 处理完上一次的操作后 , 能在O(1)时间内查找到更前一次的操作

LeetCode 20题 有效的括号

LeetCode 379题 每日温度

队列

特点

先进先出

适用场景 : 广度优先搜索

双端队列

基本实现

可以利用一个双链表

队列的头尾两端能在O(1)的时间内进行数据的查看、添加和删除

适用场景 : 实现一个长度动态变化的窗口或者连续区间

LeetCode 239题 滑动窗口最大值

树

结构直观

通过树问题来考察 递归算法

面试中常考的树的形状 :

普通二叉树

平衡二叉树

完全二叉树

二叉搜索树

四叉树

多叉树

特殊的树 : 红黑树 、自平衡二叉搜索树(不必准备太多)

考察的点 :

遍历

前序遍历

中序遍历

后序遍历

LeetCode 230题 二叉搜索中第K小的元素

高级数据结构

优先队列

图

前缀树

线段树

树状数组

优先队列

与普通队列的区别

保证每次取出的元素是队列中优先级别最高的

优先级别可自定义

本质

二叉堆的结构 , 利用一个数组结构来实现完全的二叉树

特性

数组里的第一个元素array[0]拥有最高的优先级

给定一个下标i , 那么对于元素array[i] 而言

父节点 对应的元素下标是(i-1)/2

左侧子节点 对应的元素下标是2*i+1

右侧子节点 对应的元素下标是2*i+2

数组中每个元素的优先级都必须要高于它两侧子节点

其基本操作有以下两个

向上筛选

向下筛选

适用场景 : 从杂乱无章的数据中按照一定的顺序(或者优先级)筛选数据

LeetCode 347题 前K个高频元素

图

最基本知识点如下

阶 、度

树、森林、环

有向图、无向图、完全有向图、完全无向图

连通图、连通分量

图的存储个表达方式 : 邻接矩阵、邻接链表

必须熟练掌握的知识点

图的存储和表达方式 : 邻接矩阵、邻接链表

图的遍历 : 深度优先、广度优先

二部图的检测 、树的检测、环的检测 : 有向图、无向图

拓扑排序

联合-查找算法

最短路径 : Dijkstra 、Bellman-Ford

LeetCode 785题 判断二分图

前缀树

也成字典树 , 这种数据结构被广泛地运用在字典查找当中

什么是字典查找

例如 : 给定一系列构成字典的字符串 , 要求在字典当中找出所有以"ABC"开头的字符串

方法一 : 暴力搜索法

时间复杂度 : O(M*N)

方法二 : 前缀树

时间复杂度 : O(M)

经典应用

搜索框输入搜索文字 , 会罗列以搜索词开头的相关搜索

输入法的联想输入功能

重要性质

每个节点至少包含两个基本属性

children : 数组或者集合 , 罗列出每个分支当中包含的所有字符

isEnd : 布尔值 , 表示该节点是否为某字符串的结尾

根节点是空的

除了根节点 , 其他所有节点都可能是单词的结尾 , 叶子节点一定都是单词的结尾

最基本的操作

创建

方法

遍历一遍输入的字符串 , 对每个字符串的字符进行遍历

从前缀树的根节点开始 , 将每个字符加入到节点的children字符集当中

如果字符集已经包含了这个字符 , 跳过

如果当前字符是字符串的最后一个 , 把当前节点的isEnd标记为真

搜索

方法

从前缀树的根节点出发 , 逐个匹配输入的前缀字符

如果遇到了 , 继续往下一层搜索

如果没遇到 , 立即返回

LeetCode 题212 单词搜索

线段树

一种按照二叉树的形式存储数据的结构 , 每个节点保存的都是数组里某一段的总和

LeetCode 题315 计算右侧小于当前元素的个数

树状数组

重要的基本特征

利用数组来表示多叉树的结构 , 和优先队列有些类似

优先队列是用数组来表示完全二叉树 , 而树状数组是多叉树

树状数组的第一个元素是空节点

如果节点tree[y]是tree[x]的父节点 , 那么需要满足y=x-(x&(-x))

LeetCode 题308 二维区域和检索 -可变