朱继鹏的博客

天道酬勤，全栈不停

0%

dsa

发表于 更新于 分类于
数据结构和算法

数据结构（structure）

存储结构与逻辑结构

存储结构

顺序存储结构

俗称为 数组 （array）

— 数组的分类 —

  • 普通数组
  • 环形数组
    • 环形数组队列
    • 环形缓冲（RingBuffer）

链式存储结构

链表实现可以参考这里（原创）structure-link

俗称为 链表 （link）

— 链表的概念 —

  • 元素（element）：包含各种数据的对象
  • 结点（node）：包含元素（element）和指向下一个结点（node）的指针（java中为引用）
  • 虚结点（dummy）：包含无效（invalid）元素（element）的辅助（assist）结点
  • 头结点：链表中位于头部（head）的虚结点（dummy）
  • 尾结点：链表中位于尾部（tail）的虚结点（dummy）
  • 元结点：链表中包含第一个（first）有效（valid）元素（element）的结点（node）
  • 末结点：链表中包含最后一个（last）有效（valid）元素（element）的结点（node）
  • 头指针：头结点（head）存在时指向头结点（head），不存在时指向元结点（first）
  • 尾指针：尾结点（tail）存在时指向尾结点（tail），不存在时指向末结点（last）

— 链表的分类 —

  • 单链表
    • 普通单链表
      • 普通单链表（无头结点）
      • 普通单链表（有头结点）
    • 循环单链表
      • 循环单链表（有头结点）
  • 双链表
    • 普通双链表
      • 普通双链表（有头结点，无尾结点，无尾指针）
      • 普通双链表（有头结点，有尾结点，无尾指针）
      • 普通双链表（有头结点，有尾结点，有尾指针）
    • 循环双链表
      • 循环双链表（有头结点）

对于单链表来说，尾指针和尾结点没有意义，因为在尾部删除时无法通过尾指针向前找到上一个结点
对于循环双链表来说，尾指针没有意义，尾指针可以通过头指针快速得到
对于循环双链表来说，尾结点没有意义，头结点同时也是尾结点

— 头结点的作用 —

  • 简化头部操作：无头结点时在头部添加和删除元结点需要特殊处理（需要更新head指针的引用）

— 尾结点的作用 —

  • 加快尾部操作：无尾结点时在尾部添加和删除末结点需要预先处理（需要先遍历得到tail指针）

逻辑结构

  • 可选（optional）：包含一个元素的容器（container）结构
  • 合集（collection）：包含多个元素的容器（container）结构
  • 集合（set）：无序的合集（collection）
  • 列表（list）：有序的合集（collection）
    • 队列（queue）：只支持尾部插入和头部删除的列表（list）
    • 栈列（stack）：只支持头部插入和头部删除的列表（list）
  • 字典（dict）：支持键和值快速关联的映射（mapping）结构
  • 堆（heap）：父结点比子结点大或小（兄弟结点无大小关系）的树形（tree）结构
  • 跳表（skiplist）：包含多层索引的链表（link）结构

优先级队列实现：堆
可排序字典实现：红黑树或者跳表

  • 集合结构：无依赖关系
  • 线性结构：一对一关系
  • 树形结构：一对多关系
  • 图形结构：多对多关系
  • 映射结构：映射关系

集合结构

零个或多个数据元素的无序合集（collection），俗称为 集合 （set）

线性结构

零个或多个数据元素的有序合集（collection），俗称为 线性表 （sequence table）

包含如下几种分类

  • 列表（list）：可以在任意位置插入（add）和删除（remove）
  • 队列（queue）：只能在尾部（rear）插入（enqueue）和头部（front）删除（dequeue）
  • 栈列（stack）：只能在顶部（top）插入（push）和删除（pop）

ps： 队列 的作用是 先进先出 ，常用来支持 广度优先 的操作，特点是 递进

ps： 栈列 的作用是 后进先出 ，常用来支持 深度优先 的操作，特点是 回溯

数组

数组

列表

列表实现可以参考这里（原创） structure-list

队列

队列实现可以参考这里（原创） structure-queue

栈列

栈列实现可以参考这里（原创） structure-stack

字串

字符串

树形结构

树的实现可以参考这里（原创） structure-tree
堆的实现可以参考这里（原创） structure-heap

树的三种存储方式

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

二叉树

二叉树存储：链表、数组（特别是完全二叉树）
二叉树构建：层次遍历（一个数组）、前序+中序（二个数组）、中序+后序（二个数组）
二叉树遍历：深度优先遍历（前序、中序、后序）、广度优先遍历（层次遍历）

— 二叉树的性质 —

  • 在二叉树的第j（j>=1）层至多有2^(j - 1)个结点
  • 深度为k（k>=1）的二叉树至多有2^k - 1个结点
  • 具有n (n>=0) 个结点的完全二叉树的深度为log2(n)取整 + 1
  • 对于任何一棵二叉树， 如果度为0的结点（叶结点）数为n0， 度为2的结点数为n2，则n0 ＝ n2 ＋ 1
  • 结点编号为t（t>=1）的左子结点编号为2 * t，右子结点编号为2 * t + 1，父结点编号为 t / 2 取整除法
  • 数组下标为i（i>=0）的左子结点编号为2 * i + 1，右子结点编号为2 * i + 2，父结点编号为 (i - 1) / 2 取整除法

二叉树某层最多结点数证明如下

  • 第1层时，x = 1，结点数为1 = 2^(x - 1)
  • 第2层时，x = 2，结点数最多为第1层的2倍2 = 2^(x - 1)
  • 第j层时，x = j，结点数最多为第x - 1层的2倍2^((x - 1) - 1) * 2 = 2^(x - 1)
  • 因为第j层时x = j
  • 所以第j层时用j代入x可得结点数最多为2^(x - 1) = 2^(j - 1)

二叉树最多结点数证明如下

  • 结点数为2^0 + 2^1 + … + 2^(k-2) + 2^(k-1) = 2^k - 1

二叉树n个结点的深度证明如下

  • 设深度为k
  • 因为第k层的结点数等于或大于第k-1层的结点数加1
  • 因为第k层的结点数小于第k层的结点数加1
  • 则由二叉树最多结点数性质可知(2^(k - 1) - 1) + 1 <= n < (2^k - 1) + 1
  • 则2^(k - 1) <= n < 2^k
  • 则k - 1 <= log2(n) < k
  • 则 log2(n) < k <= log2(n) + 1
  • 因为k为整数
  • 当log2(n)为整数时k = log2(n) + 1 = log2(n)取整 + 1
  • 当log2(n)为小数时k = log2(n)取整 + 1
  • 所以k为log2(n)取整 + 1

二叉树度的证明

  • 因为除了根结点，每个点都有入边
  • 所以入边数等于结点数减1为(n0 + n1 + n2) - 1
  • 而出边数等于所有结点度的和为n1 + 2n2
  • 因为入边数等于出边数
  • 则(n0 + n1 + n2) - 1 = n1 + 2n2
  • 则n0 ＝ n2 ＋ 1

ps： 入边 是 进入结点时 的边， 出边 是 从结点出去 的边

编号关系证明如下

  • 记完全二叉树中当前结点的编号为t（t>=1），层级为j（j>=1）
  • 因为第j层最左边的元素的编号等于第1层到第j-1层的所有元素个数之和再加1
  • 所以第j层最左边的元素的编号为2^0 + … + 2^(j-2) + 1 = 2^(j-1)
  • 所以第j+1层最左边的元素的编号为 2^(j+1-1) = 2^j
  • 因为t结点的左孩子编号等于第j+1层最左边的元素的编号加上t结点左边结点的孩子个数和
  • 所以t结点的左孩子编号为2^j + 2*(t-2^(j-1)) = 2 * t
  • 因为t结点的右孩子编号等于做左孩子的编号加1
  • 所以t结点的右孩子编号为2 * t + 1
  • 设t结点的的父结点编号为x
  • 则x结点左孩子编号为2 * x
  • 则x结点右孩子编号为2 * x + 1
  • 因为t结点是x结点的孩子
  • 则2 * x <= t <= 2 * x + 1
  • 则(t - 1) / 2 <= x <= t / 2
  • 因为x为整数
  • 当t为奇数时x = (t - 1) / 2 = t / 2 取整
  • 当t为偶数时x = t / 2 = t / 2 取整
  • 所以x为t / 2 取整
  • 综上t结点的左孩子编号为2 * t，右孩子编号为2 * t + 1，父结点的编号为t / 2（取整除法）

下标关系证明如下

  • 记完全二叉树中当前结点在数组中的下标为i（i>=0）
  • 由编号公式可知左孩子下标为(2 * (i + 1)) - 1 = 2 * i + 1
  • 由编号公式可知右孩子下标为(2 * (i + 1) + 1) - 1 = 2 * i + 2
  • 由编号公式可知父结点下标为((i + 1) / 2) - 1 = (i - 1) / 2
  • 综上左孩子下标为2 * i + 1，右孩子下标为2 * i + 2，父结点下标为(i - 1) / 2（取整除法）

ps：下标和编号相差1，下标转编号时需要加1，编号转下标时需要减1

— 深度和高度 —

  • 深度（k）：从上往下数（根结点到该结点的距离）
  • 高度（h）：从下往上数（该结点到叶结点的距离）
满二叉树

每层的结点都是 满 的

完全二叉树

每层的结点都是 左连续 的

线索二叉树
  • 因为除了根结点，每个结点都有一条入边，所以边数为n - 1
  • 因为每个结点都有左右两个指针域，所以指针域个数为2n
  • 所以普通二叉树浪费的空间等于指针域个数减去边数为2n - (n - 1) = n + 1
查找二叉树

BST树：查找二叉树（Binary Search Tree）

二叉树查找：等值查找、范围查找

平衡二叉树

AVL树：平衡二叉树（缩写来源于发明者的名字Adelson-Velskii和Landis）

红黑树

红黑树也是查找二叉树，可以保证大致平衡

最优二叉树

最优二叉树又叫哈夫曼树

多叉树

B树
B-树
B+树
B*树
字典树

字典树（Trie树）又叫前缀树

二叉堆

Heap：堆

  • 优先级队列
  • 延时队列
  • 定时器
  • 堆排序
  • TopK

多叉堆

跳表

图形结构

图的实现可以参考这里（原创） structure-graph

图存储：邻接矩阵、邻接表
图构建：邻接矩阵、邻接表
图遍历：深度优先遍历、广度优先遍历

映射结构

数据算法（algorithm）

算法指南

算法理论

算法评价

算法操作

基本操作

  • 基础操作
    • 遍历（枚举）
    • 递归（递推）
    • 双指针（逼近）
  • 进阶操作
    • 计数
    • 分组
    • 分桶

优化操作

  • 遍历
    • 跳跃前进
    • 提前结束
  • 排序
    • 有序处理
  • 查找
    • 二分查找
    • 映射查找

辅助操作

  • 功能：
    • 标记状态：状态 方向 已访问
    • 记录最值：最小值 最大值
    • 关联元素：关联树的父结点 保存结点的左右结点
  • 结构：
    • 一维一个数据：int boolean
    • 一维多个数据：array list set
    • 二维单个数据：array list（比如range和point可以用带两个元素的array实现）
    • 二维多个数据：二维array 两级list 两级set 两级map map内嵌套list map内嵌套set
    • 键值映射数据：
      • 一个数组（下标为key，适合key为数字且范围较小的场景）
      • 多个数组（下标为key，多个数据通过下标关联）
      • 映射结构（map）

ps： 树 的 路径 里的 起点 和 终点 成对就是二维的
ps： 图 的 坐标 里的 横坐标 和 纵坐标 成对就是二维的
ps： 区间 的 边界 里的 左边界 和 有边界 成对就是二维的

算法变量

长度变量

  • 长度 n len size
  • 行数 m rows
  • 列数 n cols

边界变量

  • 左边界 L l left
  • 中间点 M m middle
  • 右边界 R r right
  • 范围起点 B b begin
  • 范围终点 E e end

位置变量

  • 下标 i j k
  • 行标 i x
  • 列标 j y
  • 左指针 i x
  • 右指针 j y

指针变量

  • 指针 p q r u v w
  • 结点 node
  • 根结点 root
  • 头指针 head
  • 尾指针 tail

ps：链表和树用p q r，图用u v w

值类变量

  • value 值 v
  • 数值 v num
  • 字符 c ch char
  • 单词 w word
  • 字串 s str string
  • 数组 a array
  • 链表 l link
  • 点 point

辅助变量

  • 计数 c cnt
  • 临时 t tmp

其他变量

  • 求和 sum
  • 平均 avg
  • 权重 w weight

算法思想

  • 枚举
  • 递归
  • 迭代
  • 分治
  • 回溯
  • 贪心
  • 动态规划

ps：回溯和枚举都是暴力解法，可以用来求排列组合问题和最优解问题
ps：回溯是树化版的枚举，回溯依赖的操作是递归，枚举依赖的操作是遍历
ps：分治的子问题是独立的，而动态规划的子问题是非独立的

  • 排列组合问题：用回溯
  • 最优答案问题：先用贪心，不行的话再用动态规划，还是不行的话就用回溯

ps：回溯是万能解法（但会重复求解子问题，所以性能最差），动态规划则是回溯的优化，贪心则是动态规划的进一步优化
ps：回溯求组合问题时，保证后面的选项大于前面的选项，即所有的选项是有序的就可以保证不会重复
ps：在状态转移树中，若后一状态仅仅取决于上一个状态，就用贪心算法，若后一状态取决于之前的多个状态，就用动态规划算法

算法分类

按照算法结构分

集合结构

线性结构

数组
  • 合并
  • 反转（k个一组反转）
  • 轮转
  • 删除某个元素
  • 删除第k个元素（反向删除第k个元素）
  • 删除重复元素
  • 二维有序数组查找（双指针）
  • 前缀和
  • 子序列和子串
字串

字串的操作和数组一样

ps：字符串的本质还是数组

矩阵

矩阵就是二维数组，也叫做网格

链表
  • 合并
  • 反转（k个一组反转）
  • 轮转
  • 删除某个元素
  • 删除第k个元素（反向删除第k个元素）
  • 删除重复元素
  • 复制链表（带随机结点）
  • 判断链表是否有环
双指针
窗口
区间
队列
栈列

树形结构

树
  • 树相关的算法（遍历、查找）
堆
  • 堆相关的算法（堆排序、TopK）

图形结构

图
  • 图相关的算法（遍历、查找）
  • 图相关的算法（最短路径、最小生成树、旅行商问题、邮递员问题、拓扑排序、并查集）

映射结构

映射

按照算法思想分

枚举

名称：枚举算法
思想：尝试所有的可能性来得到最终的解
依赖：所有的可能性
特点：暴力尝试所有的可能性
操作：遍历
案例：求数组的最小值或者最大值

递归

名称：递归算法
思想：求解当前问题时需要先求解依赖的子问题的解
依赖：多个依赖的子问题
特点：依赖推导（自顶向下）
操作：递归
案例：求阶乘

迭代

名称：迭代算法
思想：求解当前问题时需要先求解依赖的子问题的解
依赖：多个依赖的子问题
特点：依赖推导（自底向上）
操作：迭代
案例：求阶乘

分治

名称：分治算法
思想：将大问题分解为多个独立的子问题求解后再归并结果
依赖：多个独立的子问题
特点：分解归并
操作：递归
案例：快速排序 归并排序 二分查找

回溯

名称：回溯算法
思想：选择一个分支尽可能试探到没路后就后退并继续试探其他分支
依赖：所有的可能性
特点：暴力搜索所有的可能性（减枝） + 回溯
操作：递归
案例：N皇后问题

贪心

名称：贪心算法
思想：通过当前的最优解来推导出后续的以及最终的最优解
依赖：当前的最优选择
特点：择优录取
操作：迭代
案例：最短路径问题的Dijkstra算法

ps：贪心算法可以求解局部的最优解（不一定是全局的最优解）

动态规划

名称：动态规划算法
思想：求解当前问题时需要先求解依赖的子问题的解并保存子问题的解
依赖：多个依赖的子问题
特点：依赖推导
操作：迭代或递归
案例：最短路径问题的Floyd算法

ps：动态规划可以求解全局的最优解（一定是全局的最优解）

按照算法用途分

排序算法

排序算法的分类
  • 选择类排序：选择思想
    • 简单选择排序
    • 冒泡排序
    • 堆排序
  • 插入类排序：插入思想
    • 直接插入排序
    • 二分插入排序
    • 希尔插入排序
  • 分治类排序：分治思想
    • 快速排序
    • 归并排序
    • 桶排序
  • 计数排序：排位思想
  • 基数排序：多维度排序

ps：冒泡排序的本质还是选择排序，并通过及时的将较大值交换到后面，从而巧妙的将max指针和当前值指针同步后合二为一
ps：堆排序可以理解为二分版本的冒泡排序

排序算法的逻辑
  • 简单选择排序：每次在未排序的部分里通过两两比较选择出最小值加入到已排序的部分的尾部
  • 冒泡排序：每次在未排序的部分里通过两两比较选择出最大值加入到已排序的部分的头部
  • 堆排序：每次取出堆顶部的最大值和堆的最后一个元素交换后加入到已排序的部分的头部并重新调整顶部
  • 直接插入排序：每次在未排序的部分里选择第一个元素插入到已排序的部分的正确位置
  • 二分插入排序：逻辑和直接插入排序一样，只是在查找插入位置时会使用二分查找来加快插入位置的查找过程
  • 希尔插入排序：逻辑和直接插入排序一样，只是会通过分组来优化整体的有序性从而降低整体需要的插入频率
  • 快速排序：将数组按照中轴数分为两个子数组，每个子数组又递归此操作直到只包含一个元素后就可以结束了
  • 归并排序：将数组按照中间点分为两个子数组，每个子数组又递归此操作直到只包含一个元素后就可以归并了
  • 桶排序：将数组按照区间分成多个桶排序后合并（需要依赖其他的排序算法对每个桶进行排序，比如快速排序）
  • 计数排序：计算出每个元素的数量后对每个元素累加此元素及前面的值算出每个元素的最高排位后反向填充回原数组
  • 基数排序：对元素的每个部分依次进行排序（需要依赖其他的稳定排序算法对每个维度进行排序，比如计数排序）

未排序和已排序部分说明

  • 简单选择排序中当前指针的左边数组部分是已排序部分，右边数组部分是未排序部分
  • 冒泡排序中当前指针的右边数组部分是已排序部分，左边数组部分是未排序部分
  • 堆排序中当前指针的右边数组部分是已排序部分，左边数组部分是未排序部分
  • 插入排序中当前指针的左边数组部分是已排序部分，右边数组部分是未排序部分
  • 插入排序中最开始的时候 已排序 部分会包含一个元素（一般是数组的第一个元素）

ps： 当前指针 指向的元素在处理时也属于 未排序 部分

分治类排序的分治方法对比

  • 快速排序是按照 大小 分的，其中一个子数组的元素都小于等于中轴数，另一个子数组的元素都大于等于中轴数
  • 归并排序是按照 位置 分的，其中一个子数组的元素都位于中间点左边，另一个子数组的元素都位于中间点右边
  • 桶排序则是按照 区间 分的，每个元素按照所属的区间划分到对应的桶里面
排序算法的复杂度
  • 简单选择排序
    • 平均时间复杂度为O(n^2)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n^2)
    • 空间复杂度为O(1)
  • 冒泡排序
    • 平均时间复杂度为O(n^2)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n)
    • 空间复杂度为O(1)
  • 堆排序
    • 平均时间复杂度为O(nlog2(n))
    • 最坏时间复杂度为O(nlog2(n))
    • 最好时间复杂度为O(nlog2(n))
    • 空间复杂度为O(1)
  • 直接插入排序
    • 平均时间复杂度为O(n^2)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n)
    • 空间复杂度为O(1)
  • 二分插入排序
    • 平均时间复杂度为O(n^2)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n)
    • 空间复杂度为O(1)
  • 希尔插入排序
    • 平均时间复杂度为O(n^1.3)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n)
    • 空间复杂度为O(1)
  • 快速排序：
    • 平均时间复杂度为O(nlog2(n))
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(nlog2(n))
    • 空间复杂度为O(log2(n))
  • 归并排序
    • 平均时间复杂度为O(nlog2(n))
    • 最坏时间复杂度为O(nlog2(n))
    • 最好时间复杂度为O(nlog2(n))
    • 空间复杂度为O(n)
  • 桶排序
    • 平均时间复杂度为O(n + k)
    • 最坏时间复杂度为O(n^2)
    • 最好时间复杂度为O(n)
    • 空间复杂度为O(n + k)
  • 计数排序
    • 平均时间复杂度为O(n + k)
    • 最坏时间复杂度为O(n + k)
    • 最好时间复杂度为O(n + k)
    • 空间复杂度为O(n + k)
  • 基数排序
    • 平均时间复杂度为O(n * k)
    • 最坏时间复杂度为O(n * k)
    • 最好时间复杂度为O(n * k)
    • 空间复杂度为O(n + k)

ps：快速排序的最坏情况是中轴数每次都选到了最小值或者最大值，退化为冒泡算法，所以最坏时间复杂度为 O(n^2)

ps：归并排序归并需要新的结果数组，所以空间复杂度为 O(n) + O(log2(n)) = O(n)

排序算法的稳定性
  • 简单选择排序：不稳定排序，两个相同的值在交换到右边时是倒序的肯定会导致原来的相对顺序被打乱
  • 冒泡排序：稳定排序
  • 堆排序：不稳定排序，两个相同的值在交换到右边时是倒序的肯定会导致原来的相对顺序被打乱
  • 直接插入排序：稳定排序
  • 二分插入排序：不稳定排序，二分插入相同的元素时不一定会插入到多个相同元素的最后面
  • 希尔插入排序：不稳定排序，两个相同的值分在不同的组排序后可能会导致原来的相对顺序被打乱
  • 快速排序：不稳定排序，两个相同的值在交换到右边时是倒序的肯定会导致原来的相对顺序被打乱
  • 归并排序：稳定排序
  • 桶排序：稳定排序
  • 计数排序：稳定排序
  • 基数排序：稳定排序

ps：例如简单选择排序时 5 7 5 3 1 中的两个相同5被后面的3和1换到后面时是倒序的肯定会导致原来的相对顺序被打乱

不稳定算法排序的问题举例

1
2
3
4
5
6
一个班的学生已经按照学号大小排好序了，
现在要求按照年龄从小到大再排个序，
如果年龄相同的必须按照学号从小到大的顺序排列。

如果年龄排序的方法是不稳定，
会导致年龄相同的学号又排乱了。

ps： 基数排序 这种 多维排序 就需要使用 计数排序 这种稳定排序来避免不稳定性排序导致的问题

排序算法的交换操作
  • 简单选择排序：使用，非相邻交换
  • 冒泡排序：使用，相邻交换
  • 堆排序：使用，非相邻交换
  • 直接插入排序：未使用
  • 二分插入排序：未使用
  • 希尔插入排序：未使用
  • 快速排序：使用，非相邻交换
  • 归并排序：未使用
  • 桶排序：未使用
  • 计数排序：未使用
  • 基数排序：未使用

ps：排序过程中有交换操作的，如果不是相邻交换，就不是稳定排序
ps：排序过程中有分组操作的，比如希尔插入排序，也不是稳定排序

查找算法

  • 集合结构
    • 遍历查找
  • 线性结构
    • 无序表查找
      • 遍历查找
    • 有序表查找
      • 二分查找
      • 插值查找
      • 斐波那契查找
  • 树形结构
    • 二叉查找树（红黑树）
    • 多叉查找树（B树系列）
  • 图形结构
    • 广度优先搜索（BFS）
    • 深度优先搜索（DFS）
  • 映射结构
    • 哈希查找

— 查找型数据结构 —

  • 基于内存的
    • 红黑树：例如java中的TreeMap
    • 跳表：例如java中的ConcurrentSkipListMap、redis的SortedSet
  • 基于磁盘的
    • B+树：例如数据库中的B+树索引

— 查找型数据索引 —

  • 线性索引
    • 稠密索引
    • 分块索引
    • 倒排索引
  • 树形索引
  • 哈希索引

ps：查找（find）

匹配算法

ps：匹配（match）

搜索算法

ps：搜索（search）

路径算法

调度算法

算法总结

按照算法结构总结

集合结构

线性结构

数组
  • 求两个位置的移动次数： j - i
  • 求两个位置的元素个数： j - i + 1
字串

字串的操作和数组一样

ps：字符串的本质还是数组

矩阵

矩阵就是二维数组，也叫做网格

链表

尾插法 用于正向插入
头插法 用于反向插入
快慢指针 查找链表的中点

  • 结束条件判断
    • 链表中结束条件判断时除了用p还可以用p.next和p.next.next
    • 例如在尾部添加时找到倒数第一个时使用p.next == null为结束条件
    • 例如在尾部添加时找到倒数第二个时使用p.next.next == null为结束条件
  • 前向结点引用
    • 可以用变量q来保存和记录前一个
    • 还可以用map来保存和记录前一个
双指针

双指针中一般循环条件为 i <= j ，结束条件为 i > j 代表所有的元素都处理过了
双指针中也可以是循环条件为 i < j ，结束条件为 i >= j 代表剩余一个元素时不需要处理

窗口算法

窗口算法可以用来求一个最优的区间（范围尽可能大或者尽可能小的区间）

区间算法

区间算法可以用来求多个不相交的区间

队列

队列 先进先出 按照正向顺序进行处理
队列 常用于 广度优先遍历（BFS） 时保存 待处理 的元素

栈列

栈列 后进先出 按照反向顺序进行处理
栈列 常用于 深度优先遍历（DFS） 时保存 待回退 的元素

树形结构

树

树的常见解决思路

  • 广度优先遍历（BFS）
  • 深度优先遍历（DFS）
  • 动态规划（子结点的状态只依赖父状态）

— 树的遍历算法 —

广度优先遍历可以用队列来解决（参考Tree.java中的层次遍历）
深度优先遍历可以用栈列来解决，也可以用递归来解决（参考Tree.java中的深度遍历）

  • 树的广度优先遍历的运行条件
    • 循环条件：队列不为空
    • 结束条件：队列为空
  • 树的深度优先遍历的运行条件
    • 循环条件：指针不为空或者栈列不为空
    • 结束条件：指针为空且栈列为空

ps：深度优先遍历时指针为空但栈列不为空时代表需要回溯（执行后退操作）

— 树的路径算法 —

二叉树的路径算法中生成到叶子结点的路径时需要用map来记录结点的父结点
二叉树的最近公共祖先本质上是求到两个结点的路径的公共部分

— 树的查找算法 —

查找二叉树（BST）的问题可以用中序遍历（递归和非递归都可以）来解决

堆

堆常用来求TopK的问题，常见的实现为优先级队列（PriorityQueue）

图形结构

图

图的常见解决思路

  • 广度优先遍历（BFS）
  • 深度优先遍历（DFS）
  • 动态规划（矩阵中点的状态只依赖上边和左边的点的状态）

ps：图遍历时要时刻记得过滤掉 不可访问 （ 无效点 、 无通路 ）和 已访问 的点
ps：即图遍历时要遍历那些 可访问 （ 有效点 、 有通路 ）和 未访问 的点

— 图的遍历算法 —

广度优先遍历可以用队列来解决（参考Graph.java中的层次遍历）
深度优先遍历可以用栈列来解决，也可以用递归来解决（参考Graph.java中的深度遍历）

  • 图的广度优先遍历的运行条件
    • 循环条件：队列不为空
    • 结束条件：队列为空
  • 图的深度优先遍历的运行条件
    • 循环条件：指针不为空或者栈列不为空
    • 结束条件：
      • 提前结束（到达了终点）：指针不为空或者栈列不为空
      • 完全结束（回到了起点）：指针为空且栈列为空

ps：深度优先遍历时指针为空但栈列不为空时代表需要回溯（执行后退操作）

  • 图的广度优先遍历的状态变化
    • 未访问（未处理）：初始的状态
    • 待访问（待处理）：选择某个顶点时（入队列之后）
    • 已访问（已处理）：使用某个顶点时（出队列之后）
  • 图的深度优先遍历的状态变化
    • 未访问（未处理）：初始的状态
    • 访问中（处理中）：选择某个顶点时（入栈列之前）
    • 已访问（已处理）：回退某个顶点时（出栈列之前）

ps：广度优先遍历时如果不需要判断是否存在回路时待访问和已访问可以合并为已访问状态
ps：深度优先遍历时如果不需要判断是否存在回路时访问中和已访问可以合并为已访问状态
ps：深度优先遍历时的入栈列是前进操作，作用是保存回退点
ps：深度优先遍历时的出栈列是回溯操作，作用是恢复回退点
ps：深度优先遍历时的回溯操作代表邻接点都处理完毕了

— 图的组织形式 —

  • 邻接表：指针为顶点下标或者顶点自身
    • 结构：顶点数组 + 两级list
      • 顶点：顶点数组
      • 边集：两级list
      • 边值：顶点下标
      • 权重：不支持
      • pointer：顶点下标
      • visited：array
    • 结构：两级map
      • 顶点：每级map的key是顶点
      • 边集：两级map
      • 边值：顶点自身
      • 权重：支持（两级map的value是权重）
      • pointer：顶点自身
      • visited：set（顶点集合为任意类型） 或 array（顶点集合为连续的数字）
    • 结构：结点数组
      • 顶点：结点数组（结点内部包含顶点的值）
      • 边集：每个结点内部包含的邻接点列表
      • 边值：结点自身
      • 权重：不支持
      • pointer：结点自身
      • visited：set
    • 结构：顶点数组 + 边集链表
      • 顶点：顶点数组
      • 边集：每个顶点内部包含边（边包含了当前顶点的下一条邻接边的指针）
      • 边值：顶点下标（边包含了当前顶点的邻接点在顶点数组中的下标）
      • 权重：支持（边里面可以包含权重）
      • pointer：顶点下标
      • visited：array
  • 邻接矩阵：指针为矩阵坐标
    • 结构：二维array
      • 顶点：顶点数组
      • 边集：二维array
      • 边值：顶点下标
      • 权重：支持（二维array的value是权重）
      • pointer：矩阵坐标
      • visited：二维array
    • 结构：两级map
      • 顶点：顶点数组
      • 边集：两级map
      • 边值：顶点下标
      • 权重：支持（两级map的value是权重）
      • pointer：矩阵坐标
      • visited：两级map

映射结构

映射

映射可以用数组实现，此时key是数值类型（数组的下标）
映射可以用map实现，此时key是任意类型

按照算法思想总结

  • 回溯算法：求所有的解（也可以求全局的最优解，是万能的解法）
  • 贪心算法：求局部的最优解（不一定是全局的最优解，不一定是正确的答案）
  • 动态规划：求全局的最优解（一定是全局的最优解，一定是正确的答案）

递归

递归的通用写法11

  1. 判断是否需要结束并返回
  2. 前进时处理业务逻辑
  3. 递归调用方法

递归的通用写法12

  1. 判断是否需要结束并返回
  2. 递归调用方法
  3. 回溯时处理业务逻辑

递归的通用写法21

  1. 前进时处理业务逻辑
  2. 判断是否需要继续并递归调用方法

递归的通用写法22

  1. 判断是否需要继续并递归调用方法
  2. 回溯时处理业务逻辑

回溯

回溯的通用写法1

  1. 判断是否需要结束并将结果添加到列表后返回
  2. 处理业务逻辑
  3. 循环遍历所有分支
  4. 在循环中前进时记录路径
  5. 在循环中前进时记录状态
  6. 在循环中递归调用方法
  7. 在循环中回溯时撤销路径（如果是数组就不需要撤销，下次用的时候会覆盖）
  8. 在循环中回溯时撤销状态

回溯的通用写法2

  1. 处理业务逻辑
  2. 循环遍历所有分支
  3. 在循环中前进时记录路径
  4. 在循环中前进时记录状态
  5. 在循环中判断是否需要继续并递归调用方法
  6. 在循环中回溯时撤销路径（如果是数组就不需要撤销，下次用的时候会覆盖）
  7. 在循环中回溯时撤销状态

回溯的参数写法

  • 第一部分为3个
    • 第1个为步骤的计数（一般从0而不是1开始）
    • 第2个为步骤的总数（可选，如果可以通过其他部分获得的话就是可选的）
    • 第3个为步骤的选项（可选，如果可以通过其他部分获得的话就是可选的）
  • 第二部分为原始数据
  • 第三部分为辅助信息
    • 访问状态（visited）
    • 访问轨迹（trail）
    • 当前状态（state）
  • 最后一部分为结果数据
    • 当前结果（可选，主要用于和已有的最优结果进行比较从而进行剪枝操作）
      • 和
      • 差
      • 最小值
      • 最大值
      • 平均值
    • 最终结果
      • 单个值
      • 值列表
      • 路径

算法重点

  • 结构
    • 线性结构
      • 单调栈
      • 最小栈
    • 树形结构
      • 线索树
      • 平衡树
      • 红黑树
      • 最优树（哈夫曼树）
      • 字典树（前缀树）
    • 图形结构
      • 最短路径（Dijkstra和Floyd）
      • 最小生成树（Prim和Kruskal）
      • 旅行商问题（访问所有点且不允许重复访问）
      • 邮递员问题（访问所有点且允许重复访问）
      • 拓扑排序
      • 并查集
  • 思想
    • 动态规划dp（状态压缩）
  • 用途
    • 字符串匹配算法（KMP）
  • 专题
    • 前缀和
    • TopK
  • 难点
    • 子序列和子串
只想买包辣条