程序猿攻城狮：一位攻城狮的自我算法修养

程序猿攻城狮：一位攻城狮的自我算法修养

程序员需要掌握的算法

• 数据结构与算法
• 算法基础
• 基础数据结构
• 数组
• 栈与队列
• 线性表
• 哈希表(散列表)
• 树
• 图
• 常见算法
• 十大排序算法
• 图论算法
• 搜索与回溯算法
• 动态规划
• 字符串匹配算法
• 流相关算法

数据结构与算法

• 基本算法思想
• 动态规划
• 贪心算法
• 回溯算法
• 分支算法
• 枚举算法

算法基础

• 时间复杂度
• 空间复杂度
• 最大复杂度
• 平均复杂度

基础数据结构数组

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

栈与队列

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

线性表

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

哈希表(散列表)

• 散列函数
• 碰撞解决办法:开放地址法链地址法再次哈希法建立公共溢出区
• 布隆过滤器
• 位图
• 动态扩容

树

• 二叉树: 各种遍历 递归与非递归二叉查找树平衡二叉树平衡二叉搜索树AVL树红黑树完全二叉树
• 多路查找树B树B 树2-3树2-3-4树
• 哈夫曼树与编码
• 前缀树
• 线段树
• 堆小顶堆大顶堆二项堆优先队列斐波那契堆

图

• 图的存储
• 邻接矩阵
• 邻接表
• 关键路径
• 最小生成树
• 最短路径
• 拓扑排序

常见算法十大排序算法

• 简单排序:
• 插入排序
• 选择排序
• 冒泡排序
• 分值排序:
• 快速排序 : 注意轴的选取方式
• 归并排序
• 分配排序:
• 桶排序
• 基数排序
• 树状排序:
• 堆排序
• 计数排序
• 希尔排序

图论算法

• 图的表示:
• 邻接矩阵
• 邻接表
• 遍历算法:
• 深度搜索
• 广度搜索
• 查找算法:
• 二分查找
• 散列表查找
• 树结构查找
• 最短路径算法:
• Floyd
• Dijkstra
• 最小生成树算法:
• Prim
• Kruskal
• 实际常用算法:
• 关键路径
• 拓扑排序
• 二分图匹配:
• 配对算法
• 匈牙利算法
• 拓展:
• 中心性算法
• 社区算法
• 并查集

搜索与回溯算法

• 贪心算法
• 启发式搜索算法:
• A*寻路算法
• 地图着色算法
• N皇后问题
• 最优加工算法
• 旅行商问题

动态规划

• 树形DP:01背包问题
• 线性DP:最长公共子序列最长公共子串
• 区间DP:矩阵最大值矩阵最大和矩阵最大积
• 数位DP:数字游戏
• 状态压缩DP:旅行商

字符串匹配算法

• 正则表达式
• 暴力匹配算法
• 模式匹配:KMPBoyer-MooreTrie

流相关算法

• 最大流:
• 最短增广路
• Dinic算法
• 最大流最小割:
• 最大收益问题
• 方格取数问题
• 最小费用最大流:
• 最小费用里
• 消遣