基本概念

  • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。


逻辑结构

  • 逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。
  • 分为线性结构和非线性结构
    • 集合：除了“同属于一个集合”的关系外，别无其他关系。类似于数学上的集合。
    • 线性结构：一对一。比如排队
    • 树形结构：一对多。比如家族族谱
    • 图状结构或网状结构：多对多。比如地图


物理结构

  • 也称为存储结构（映像）。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

    • 顺序存储：存储的物理位置相邻。（物理位置即信息在计算机中的位置）
    • 链接存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。
    • 索引存储：类似于目录。
    • 散列存储：通过关键字直接计算出元素的物理地址。

      算法的复杂度

  • 时间复杂度：

    • 用来衡量算法随着问题规模增大，算法执行时间增长的快慢；
    • 是问题规模的函数：T(n)是时间规模函数，时间复杂度主要分析T(n)的数量级。
    • T(n)=O(f(n)) f(n) 是算法中基本运算的频度，一般我们考虑最坏情况下的时间复杂度。
  • 空间复杂度
    • 它用来衡量算法随着问题规模增大，算法所需空间的快慢。
    • 是问题规模的函数：S(n)=O(g(n))；算法所需空间的增长率和g(n)的增长率相同。
  • 时间复杂度计算
    • 单个循环体：直接关注循环体的执行次数
    • 多个循环体：乘法规则和加法规则

数组、字符串

  • 数组的优点在于：
    • 构建非常简单
    • 能在 O(1) 的时间里根据数组的下标（index）查询某个元素

  • 而数组的缺点在于：

    • 构建时必须分配一段连续的空间
    • 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）
    • 删除和添加某个元素时，同样需要耗费 O(n) 的时间

  • LeetCode-242

链表（LinkedList）

  • 链表的优点如下：
    • 链表能灵活地分配内存空间；
    • 能在 O(1) 时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。
  • 链表的缺点是：
    • 不像数组能通过下标迅速读取元素，每次都要从链表头开始一个一个读取；
    • 查询第 k 个元素需要 O(k) 时间。
  • 经典解法：
    • 快慢指针
    • 构建一个虚假的链表头
  • 头结点和头指针的区别
    • 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。


  • LeetCode-25


单链表

  • 插入：需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。

    current 为插入节点的前驱节点 new->next = current->next current->next = new

  • 删除：从链表中删除一个元素，讲待删除元素的前驱结点指向待删除元素的后继节点，同时将待删除元素指向null，元素就删除成功了

    current为要删除节点的前驱节点 current->next = current->next->next


双链表

  • 每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

  • 插入：插入一个节点时，需要指出该节点正确的前驱和后继。

    current为插入节点的前驱节点 new->next = current->next current->next->previous = new current->next = new new->previous = current

  • 删除：双向链表的删除操作比单向链表的效率高，因为不需要再朝招前驱节点了。

    current为要删除的节点 current->previous->next = current->next current->next->previous = current->previous current->previous = null current->next = null

循环链表

  • 循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:head.next = head，这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成了一个循环链表。

栈（Stack）

  • 后进先出（LIFO），只允许在一端进行插入和删除操作。
  • 栈顶（Top）：线性表允许进行插入和删除的那一端。
  • 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
  • 可以利用一个单链表来操作栈的数据结构
  • 应用场景：在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。
  • 如果打算用一个数组外加一个指针来实现相似的效果，那么，一旦数组的长度发生了改变，哪怕只是在最后添加一个新的元素，时间复杂度都不再是 O(1)，而且，空间复杂度也得不到优化。
  • 栈的应用：
    • 括号匹配
    • 表达式求和
    • 递归
      • 阶乘
      • 斐波那契数列


  • LeetCode-20
  • LeetCode-739


队列（Queue）

  • 先进先出（FIFO），只允许在一端进行插入，另一端进行删除的线性表。
  • 队头（Front）：允许删除的一端，又称为队首。
  • 队尾（Rear）：允许插入的一端。
  • 可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，而双链表的尾指针允许我们在队尾查看和添加数据。
  • 广度优先搜索（Breadth-First Search）是运用队列最多的地方


双端队列（Deque）

  • 特点：双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。
  • 实现：与队列相似，我们可以利用一个双链表实现双端队列。
  • 应用场景：双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。


  • LeetCode-239.


树（Tree）

  • 树是递归定义的结构。

  • 结点

    • 根节点：树只有一个根节点
    • 结点的度：结点拥有的子树的数量
      • 度为0：叶子结点或者终端结点
      • 度不为0：分支节点或者非终端结点

        树的形状

  • 普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树、多叉树。

  • 红黑树、自平衡二叉搜索树。

    树的遍历

  • 前序遍历（Preorder Traversal）

  • 中序遍历（Preorder Traversal）
  • 后序遍历（Preorder Traversal）

  • 层序遍历

  • LeetCode-230

优先队列（Priority Queue）

  • 能保证每次取出的元素都是队列中优先级别最高的。
  • 优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是其他元素的子节点，而且，每个父节点只能有两个子节点，很像一棵二叉树的结构。


  • 三个重要的性质。

    • 数组里的第一个元素 array[0] 拥有最高的优先级别。
    • 给定一个下标 i，那么对于元素 array[i] 而言：
      • 它的父节点所对应的元素下标是 (i-1)/2
      • 它的左孩子所对应的元素下标是 2×i + 1
      • 它的右孩子所对应的元素下标是 2×i + 2
    • 数组里每个元素的优先级别都要高于它两个孩子的优先级别。

  • 最基本的操作有两个。

    • 向上筛选（sift up / bubble up）

当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。
不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。
时间复杂度：由于二叉堆是一棵完全二叉树，并假设堆的大小为 k，因此整个过程其实就是沿着树的高度往上爬，所以只需要 O(logk) 的时间。

  • 向下筛选（sift down / bubble down）

当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。
将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。
时间复杂度：整个过程就是沿着树的高度往下爬，所以时间复杂度也是 O(logk)。

图（Graph）

  • 最基本的知识点如下。
    • 阶（Order）、度：出度（Out-Degree）、入度（In-Degree）
    • 树（Tree）、森林（Forest）、环（Loop）
    • 有向图（Directed Graph）、无向图（Undirected Graph）、完全有向图、完全无向图
    • 连通图（Connected Graph）、连通分量（Connected Component）
    • 存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）


  • 必会知识点
    • 图的存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
    • 图的遍历：深度优先、广度优先
    • 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图
    • 拓扑排序
    • 联合-查找算法（Union-Find）
    • 最短路径：Dijkstra、Bellman-Ford


图的遍历

  • 深度优先遍历
    • 深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法
      • 空间复杂度：由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)
      • 时间复杂度：1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度为O(|V|+|E|) 2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|2)
  • 广度优先遍历
    • 广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法
      • 空间复杂度：BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。
      • 时间复杂度： 1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂度为O(|V|+|E|) 2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|2)
  • LeetCode-785

前缀树（Trie）

  • 字典树

    性质

  1. 每个节点至少包含两个基本属性。
    1. children：数组或者集合，罗列出每个分支当中包含的所有字符
    2. isEnd：布尔值，表示该节点是否为某字符串的结尾。
  2. 前缀树的根节点是空的。

所谓空，即只利用到这个结点的children属性，即只关心在这个字典里，有哪些打头的字符。

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

实现

  • 前缀树最基本的操作就是两个：创建和搜索。

    创建

  • 遍历一遍输入的字符串，对每个字符串的字符进行遍历。

  • 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中。
  • 如果字符集已经包含了这个字符，则跳过。

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

    搜索

  • 从前缀树的根节点触发，逐个匹配输入的前缀字符，如果遇到了就继续往下搜索，如果没遇到，就立即返回。

  • LeetCode-212.

线段树（Segment Tree）

  • 线段树，就是一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和。
  • 适用于数据很多，而且需要频繁更新并求和的操作。

  • 时间复杂度 O(logn)。

  • LeetCode-315.

树状数组（Fenwick Tree/Binary Indexed Tree）

  • 树状数组的数据结构有以下几个重要的基本特征。
    • 它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树。
    • 树状数组的第一个元素是空节点。
    • 如果节点 tree[y] 是 tree[x] 的父节点，那么需要满足条件：y = x - (x & (-x))。