程序员面试必须掌握的8种数据结构

程序员面试必须掌握的8种数据结构，如队列Queue：FIFO先进先出的顺序存储线性数据结构，超市结账，看看你会不会。

数据结构

• 图Graph,不常考
  • 定义
    • 用网络形式相互连接的节点
  • 术语
    • 顶点：节点
    • 边：edge，一对节点
    • 权重/成本
  • 类型
    • 有向图
    • 无向图
  • 表示方式
    • 邻接矩阵
    • 邻接表
  • 遍历算法
    • 广度优先搜索DFS
    • 深度优先搜索TFS
  • 面试相关
    • 实现广度和深度优先搜索
    • 检查图是否为树
    • 计算图的边数
    • 找到两个顶点之间的最短距离
• 单调栈monotone stack很少考
• 双端队列Deque，很少考
• 并查集Union Find很少考
• 线段树，很少考
• 树状数组Binary Indexed Tree，BIT，很少考
• 字典树Trie，很少考
  • 定义
    • 也称：前缀树，特殊的树状数据结构
  • 用途
    • 解决字符串相关问题很有效
    • 提供快速检索
    • 搜索字典中的单词
    • 搜索引擎中自动提供建议
    • 用于IP的路由
  • 面试
    • 计算字典树中的总单词数
    • 打印存储在字典树中的所有单词
    • 使用字典树对数组中的元素进行排序
    • 使用字典树从字典中形成单词
    • 构建T9字典：字典树+DFS
• 散列表/Hash Map 哈希表,常考
  • 定义
    • 键值对的形式存储唯一标识的对象
    • 字典：键值对的集合
    • 使用键key搜索对象value
    • Java 中的 HashSet / HashMap，C++ 中的 unordered_map，Python 中的 dict
  • 支持操作:O(1) Insert / O(1) Find / O(1) Delete
  • 哈希表的工作原理
    • <br>工作原理：对于set。key通过hash函数得到一个index，然后把value存在数组里。<br>对于get，通过key和hash函数求出index，得到value。
  • 为什么 hash 上各种操作的时间复杂度不能单纯的认为是 O(1) 的
    • key可以是字符串，整数等未知长度的东西。所以用O(L)合适；任何操作的时间复杂度从严格意义上来说 都是 O(keySize) 而不是 O(1)<br>
  • 哈希函数该如何实现
    • 128 哈希函数
  • 哈希冲突（Collision）该如何解决
    • 冲突（Collision），是说两个不同的 key 经过哈希函数的计算后，得到了两个相同的值。解决冲突的方法，主要有两种：<br>开散列法（Open Hashing）。是指哈希表所基于的数组中，每个位置是一个 Linked List 的头结点。这样冲突的 <key, value> 二元组，就都放在同一个链表中。<br>闭散列法（Closed Hashing）。是指在发生冲突的时候，后来的元素，往下一个位置去找空位<br>
  • 如何让哈希表可以不断扩容？
    • 129 重哈希
  • 性能因素
    • 哈希函数
    • 哈希表大小
    • 碰撞处理方法
  • 面试
    • 数组中查找对称的键值对
    • 是否会灵活的使用哈希表解决问题
    • 是否熟练掌握哈希表的基本原理
    • 追踪便利的完整路径
    • 查找数组是否是另一个数组的子集
    • 检查给定的数组是否不相交
    • 526. 负载均衡器<br>
    • 134. LRU缓存策略<br>657. Insert Delete GetRandom O(1)<br>954. Insert Delete GetRandom O(1) - Duplicates allowed<br>209. 第一个只出现一次的字符
    • Data Stream类问题<br>960. First Unique Number in a Stream II<br>138. 子数组之和<br>105. 复制带随机指针的链表<br>171. 乱序字符串<br>124. 最长连续序列
• 排序查找
  • 排序是为了更好的查找
  • 排序
    • 插入排序
    • 快速排序
    • 选择排序
    • 归并排序
    • 基数排序
    • 堆排序
  • 查找
    • 静态查找表
    • 动态查找表
    • 哈希表
• 数据结构定义：数据结构可以认为是一个数据存储集合以及定义在这个集合上的若干操作(功能)
  • 考法1：问某种数据结构的基本原理，并要求实现
  • 例题:说一下 Hash 的原理并实现一个 Hash 表
  • 考法2:使用某种数据结构完成事情
  • 例题:归并 K 个有序数组
  • 考法3:实现一种数据结构，提供一些特定的功能
  • 例题:最高频 K 项问题
• 时间复杂度：
  • 对多个接口的时间复杂度进行描述<br>
  • 比如你需要设计一个 Set 的数据结构
    • 算法1:O(n) lowerBound O(1) add
      • 实现方法：使用数组存储，每次打擂台进行比较，插入就直接插入到数组最后面
    • 算法2:O(logn) lowerBound O(logn) add
      • 实现方法：使用红黑树(Red-black Tree)存储，Java 里的 TreeSet，C++ 里的 map
• 数组Array，最常考
  • 类型
    • 一维数组
    • 二维数组
    • 多维数组
    • 子数组
      • 数组一部分
      • 面试题
        • 41. 42,43,最大子数组<br>44. 最小子数组<br>138. 子数组之和
    • 数组区间问题
      • 面试题
        • 30. 插入区间<br>793. 多个数组的交集<br>156. 合并区间
    • 外排序问题
      • 定义：外排序算法（External Sorting），是指在内存不够的情况下，如何对存储在一个或者多个大文件中的数据进行排序的算法。<br>
      • 两个基本步骤：<br>将大文件切分为若干个个小文件，并分别使用内存排好序<br>使用K路归并算法（k-way merge）将若干个排好序的小文件合并到一个大文件中
      • 面试题
        • 486. Merge K Sorted Arrays<br>104. Merge K Sorted Lists
    • 位运算
      • 定义：对二进制位的运算
      • 面试题
        • 365. 二进制中有多少个1<br>
    • 树状数组很少考
      • 又名:Fenwick Tree 英文名字：Binary Indexed Tree 简写:BIT 基于前缀和信息来实现<br>
      • 虽然名字叫做 Tree，但是是用数组(Array)存储的<br>BIT 是一棵多叉树，父子关系代表包含关系<br>用 getPrefixSum(k) 实现 getRangeSum(x, y)
      • 时间复杂度
        • Log(n) 修改任意位置值<br>Log(n) 查询任意区间和
      • 功能特性
        • 对于一个有 N 个数的数组，支持如下功能:<br>update(index, val) // logN 的时间内更新数组中一个位置上的值 getPrefixSum(k) // log(K) 的时间内获得数组中前 K 个数的和
      • 面试题
        • 817. 范围矩阵元素和-可变的<br>249. 统计前面比自己小的数的个数
  • 操作
    • 增get
    • 删delete
    • 插入insert、
    • 大小size
  • 面试相关
    • 寻找数组中第二小的元素
    • 找第一个不重复的整数
    • 重新排列数组中的正负值
    • 65. 两个排序数组的中位数，难题<br>
    • 6. 合并排序数组 II<br>64. 合并排序数组<br>839. 合并两个排序的间隔列表<br>486. Merge K Sorted Arrays<br>577. 合并K个排序间隔列表<br>547. 两数组的交集<br>548. 两数组的交集 II<br>793. 多个数组的交集<br>654. 稀疏矩阵乘法<br>931. Median of K Sorted Arrays<br>149. 买卖股票的最佳时机<br>405. 和为零的子矩阵<br>944. Maximum Submatrix<br>943. Range Sum Query - Immutable<br>665. 平面范围求和 -不可变矩阵<br>840. 可变范围求和
• 栈Stack，不常考
  • 定义
    • 后进先出LIFO。比如物流装车，后装的货物先卸
  • 支持操作:O(1) Push / O(1) Pop / O(1) Top
  • 应用
    • 用于非递归的遍历二叉树，计算逆波兰表达式，等等。
    • 非递归实现DFS的主要数据结构
    • 在宽度优先搜索(BFS）中，记录待扩展的节点。
    • 队列可用于实现消息队列（message queue），以完成异步（asynchronous）任务。
    • 当消息生产和消费的速度不一致时，就需要消息队列，临时保存那些已经发送而并未接收的消息。
  • 实现栈方式
    • 用一个存储结构（常用数组，偶见链表），存储元素
    • 用一个数组实现三个栈？
    • 用两个队列实现一个栈？<br>
    • 区别
      • 数组对随机访问有较好性能。<br>链表对插入和删除元素有较好性能。
    • 练习题<br>
      • lintcode: 495. 实现栈
      • 494. 双队列实现栈<br>
      • 224. 用一个数组实现三个栈<br>
  • 操作
    • push，顶部插入元素
    • pop返回并且移除栈顶元素
    • isEmpty栈是空，返回true
    • top返回顶部元素，但不移除它
    • Java，使用java.util.Stack，它是扩展自Vector类，支持push()，pop()，peek()，empty()，search()等操作。
    • C++，使用<stack>中的stack即可，方法类似Java，只不过C++中peek()叫做top()，而且pop()时，返回值为空。
    • Python，直接使用list，查看栈顶用[-1]这样的切片操作，弹出栈顶时用list.pop()，压栈时用list.append()。<br>
  • 面试相关
    • 使用栈计算后缀表达式
    • 对栈的元素进行排序
    • 判断表达式是否括号平衡
• 队列Queue，常考
  • 定义
    • FIFO先进先出的顺序存储线性数据结构，超市结账
  • 支持操作:&nbsp; &nbsp; O(1) Push / O(1) Pop / O(1) Top
  • 应用
    • 用作 BFS 算法的主要数据结构
  • 操作
    • enqueue队列尾部插入元素
    • dequeue移除队列头部元素
    • isEmpty对列为空，返回true
    • top返回队列的第一个元素
  • 实现方式
    • 用链表实现队列？
    • 用两个栈实现一个队列？<br>
    • 用循环数组实现队列？
      • 练习题：955. Implement Queue by Circular Array<br>
  • 面试
    • 使用队列表示栈
    • 对队列的前面k个元素倒序
    • 使用队列生成1到n的二进制数
    • 642. Moving Average from Data Stream<br>
    • 955. Implement Queue by Circular Array<br>
• 链表Linked List，常考
  • 定义
    • 节点链：每个节点包含数据和指向后续节点的指针
  • 用途
    • 实现文件系统，哈希表，邻接表
  • 类型
    • 单向链表
    • 双向链表
  • 操作
    • insertAtEnd
    • insertAtHead
    • Delete
    • DeleteAtHead
    • Search
    • isEmpty,为空，返回true
  • 面试
    • 反转链表
    • 检测链表中的循环
    • 返回链表倒数第n个节点
    • 删除链表中重复项
• 树Tree
  • 定义
    • 层级式的数据结构
    • 顶点和边组成
    • 树中没有图中的环路
  • 术语
    • root根节点
    • parent父节点
    • child子节点
    • leaf叶子节点
    • sibling兄弟节点
  • 类型
    • N元树
    • 线段树，基本不考，万能的
    • 二叉树，常考
      • 二叉搜索树
        • 定义：左子树小于根节点，根节点小于右子树。效果就是：左边永远小于右边
      • 平衡二叉树
        • 平衡树(AVL树)
          • 定义：
            • 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
          • 实现方法
            • 红黑树、AVL、替罪羊树、Treap、伸展树
        • 堆
          • 定义：堆是一种平衡二叉树，父节点小于子节点，多余的子节点尽可能的放在左子节点，左右子节点无大小关系。可以用数组实现<br>
          • 支持操作:O(log N) Add / O(log N) Remove / O(1) Min or Max
          • Max Heap vs Min Heap
          • 值特性：对于min堆，父节点小于子节点，左右子节点无大小关系；对于max类型堆，父节点大于子节点，左右子节点无大小关系；
          • 结构特性：是个二叉树，高度logN
          • 时间复杂度：delete, pop 复杂度都是logN，求min,or max复杂度O(1)<br>
          • 插入方法：永远从左侧插入，保证是一个平衡二叉树，如果插入数字小，那就上移，父节点下移。所以复杂度最大就是logN<br>
          • 删除方法类似
          • 实现方法：练习题：lintcode 130 heapify<br>
          • 面试练习题
            • 104. Merge K Sorted Lists<br>612. K个最近的点<br>545. 前K大数 II<br>613. 优秀成绩<br>486. Merge K Sorted Arrays<br>81. 数据流中位数<br>544. 前K大数<br>401. 排序矩阵中的从小到大第k个数
      • 线段树 Segment Tree<br>
        • 定义：线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。<br>
        • 备注：基本不考，但是如果能掌握，可以一口气解决一大堆问题 线段树是基于分治法实现的，可以作为很好的分治法的练习
  • 面试
    • 求二叉树高度
    • 在二叉搜索树中查找第k个最大值
    • 查找和根节点距离k的节点
    • 在二叉树中查找给定节点的祖先节点
    • 104. Merge K Sorted Lists<br>
      • 3种方法
        • 方法一:使用 PriorityQueue
        • 方法二:类似归并排序的分治算法
        • 方法三:自底向上的两两归并算法
      • 时间复杂度均为 O(NlogK)
• 结合:九章算法 整理而成
• 练习题都是lintcode的题