程序员必须掌握的数据结构和算法

2019 精帖
0 132

原文链接:https://www.zhihu.com/question/23148377?sort=created 

算法基础
  1. 时间复杂度
  2. 空间复杂度
 基础数据结构
  1. 线性表
    1. 列表(必学)
    2. 链表(必学)
    3. 跳跃表(知道原理,应用,最后自己实现一遍)
    4. 并查集(建议结合刷题学习)
  2. 栈与队列
    1. 栈(必学)
    2. 队列(必学)
    3. 优先队列、堆(必学)
    4. 多级反馈队列(原理与应用)
  3. 哈希表(必学)
    1. 碰撞解决方法:开放定址法、链地址法、再次哈希法、建立公共溢出区(必学)
    2. 布隆过滤器(原理与应用)
    1. 二叉树:各种遍历(递归与非递归)(必学)
    2. 哈夫曼树与编码(原理与应用)
    3. AVL树(必学)
    4. B 树与 B+ 树(原理与应用)
    5. 前缀树(原理与应用)
    6. 红黑树(原理与应用)
    7. 线段树(原理与应用)
  4. 数组
    1. 树状数组
    2. 矩阵(必学)
各种常见算法 
  1. 十大排序算法
    1. 简单排序:插入排序、选择排序、冒泡排序(必学)
    2. 分治排序:快速排序、归并排序(必学,快速排序还要关注中轴的选取方式)
    3. 分配排序:桶排序、基数排序
    4. 树状排序:堆排序(必学)
    5. 其他:计数排序(必学)、希尔排序
  2. 图论算法
    1. 图的表示:邻接矩阵和邻接表
    2. 遍历算法:深度搜索和广度搜索(必学)
    3. 最短路径算法:Floyd,Dijkstra(必学)
    4. 最小生成树算法:Prim,Kruskal(必学)
    5. 实际常用算法:关键路径、拓扑排序(原理与应用)
    6. 二分图匹配:配对、匈牙利算法(原理与应用)
    7. 拓展:中心性算法、社区发现算法(原理与应用)
  3. 搜索与回溯算法
    1. 贪心算法(必学)
    2. 启发式搜索算法:A*寻路算法(了解)
    3. 地图着色算法、N 皇后问题、最优加工顺序
    4. 旅行商问题
  4. 动态规划
    1. 树形DP:01背包问题
    2. 线性DP:最长公共子序列、最长公共子串
    3. 区间DP:矩阵最大值(和以及积)
    4. 数位DP:数字游戏
    5. 状态压缩DP:旅行商
  5. 字符匹配算法
    1. 正则表达式
    2. 模式匹配:KMP、Boyer-Moore
  6. 流相关算法 
    1. 最大流:最短增广路、Dinic 算法
    2. 最大流最小割:最大收益问题、方格取数问题
    3. 最小费用最大流:最小费用路、消遣
留言(0)
加载更多
猜你喜欢