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

硅谷探秘者 1129 0 0

原文链接: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. 最小费用最大流:最小费用路、消遣
猜你喜欢
数据结构与算法 4275 堆排(英语:Heapsort)是指利用堆这种所设计一种排。堆是一个近似完全二叉树,并同时满足堆积性质:即子键值或索引总是小于(或者大于)它父节点。以最小堆为例下沉操
数据结构与算法 823 思想该使用递归实现,思路为:每次递归将待排组在中间位置分成左右两组,分别对左右两个组进行归并排,递归条件是组长度大于等于3,所以当组中只有两个时候可以直接进行比较排
数据结构与算法 780 思想:对冒泡排一种改进,每次从没有排集合a中拿取一个最大或最小元素,放入有集合b中,直到a集合中元素被取完描述:用变量i遍历整个组,用变量j遍历i后面组,每次遍历i初始
数据结构与算法 713 思想:把所有需要排分成两个集合,一个是待排集合,一个是已排集合,每次从未排集合顺或随机拿取一个,把它加入到已排集合使其有,直到未排集合中被取走完,
数据结构与算法 962 prim(普里姆)求出。对于任何一个,理解实现只是一个方面,更重要是要明白它应用范围或应用场景,最小生成树应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 905 思想将待排集合以该集合中随机一个为分界点分成左右两个集合,一次排使其右边集合全部大于左边集合,然后再分别递归式对左右两个集合执行上述排操作,直到递归集合没有,递归束完
数据结构与算法 753 思想:希尔排是插入排增强版,其主要思想还是插入排思想。描述:在插入排基础上,对待排组进行间隔为inc分组,然后对每个分组进行直接插入排,一次排完成后,减小inc
数据结构与算法 1608 广度优先搜索(dfs、深搜)java实现-用邻接矩阵表示图定点之间关系如下图:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。