数据结构与算法

• 根本算法思维

  • 动静布局
  • 贪婪算法
  • 回溯算法
  • 分治算法
  • 枚举算法

算法根底

• 工夫复杂度
• 空间复杂度
• 最大复杂度
• 均匀复杂度

根底数据结构

数组

• 动静数组
• 树状数组
• 矩阵

栈与队列

• 栈
• 队列
• 阻塞队列
• 并发队列
• 双端队列
• 优先队列
• 堆
• 多级反馈队列

线性表

• 程序表

• 链表

  • 单链表
  • 双向链表
  • 循环链表
  • 双向循环链表
• 跳跃表
• 并查集

哈希表 (散列表)

• 散列函数

• 碰撞解决办法:

  • 凋谢地址法
  • 链地址法
  • 再次哈希法
  • 建设公共溢出区
• 布隆过滤器
• 位图
• 动静扩容

树

• 二叉树: 各种遍历, 递归与非递归

  • 二叉查找树
  • 均衡二叉树

  • 均衡二叉搜寻树

    • AVL 树
    • 红黑树
  • 齐全二叉树

• 多路查找树

  • B 树
  • B+ 树
  • 2-3 树
  • 2-3-4 树
• 哈夫曼树与编码
• 前缀树
• 线段树

• 堆

  • 小顶堆
  • 大顶堆
  • 二项堆
  • 优先队列
  • 斐波那契堆

图

• 图的存储

  • 邻接矩阵
  • 邻接表
• 要害门路
• 最小生成树
• 最短门路
• 拓扑排序

常见算法

十大排序算法

• 简略排序:

  • 插入排序
  • 抉择排序
  • 冒泡排序

• 分治排序:

  • 疾速排序 : 留神轴的选取形式
  • 归并排序

• 调配排序:

  • 桶排序
  • 基数排序

• 树状排序:

  • 堆排序
• 计数排序

• 希尔排序

  图论算法

• 图的示意:

  • 邻接矩阵
  • 邻接表

• 遍历算法:

  • 深度搜寻
  • 广度搜寻

• 查找算法:

  • 二分查找
  • 散列表查找
  • 树结构查找

• 最短门路算法:

  • Floyd
  • Dijkstra

• 最小生成树算法:

  • Prim
  • Kruskal

• 理论罕用算法:

  • 要害门路
  • 拓扑排序

• 二分图匹配:

  • 配对算法
  • 匈牙利算法

• 拓展:

  • 核心性算法
  • 社区算法

  • 并查集

    搜寻与回溯算法

• 贪婪算法

• 启发式搜索算法:

  • A* 寻路算法
• 地图着色算法
• N 皇后问题
• 最优加工算法

• 旅行商问题

  动静布局

• 树形 DP:

  • 01 背包问题

• 线性 DP:

  • 最长公共子序列
  • 最长公共子串

• 区间 DP:

  • 矩阵最大值
  • 矩阵最大和
  • 矩阵最大积

• 数位 DP:

  • 数字游戏

• 状态压缩 DP:

  • 旅行商

    字符串匹配算法

• 正则表达式
• 暴力匹配算法

• 模式匹配:

  • KMP
  • Boyer-Moore

  • Trie

    流相干算法

• 最大流:

  • 最短增广路
  • Dinic 算法

• 最大流最小割:

  • 最大收益问题
  • 方格取数问题

• 最小费用最大流:

  • 最小费用路
  • 消遣