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

2019 精帖
0 104

原文链接: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)
加载更多
猜你喜欢
  • blog -分解

    题目描述思路:枚举,只需要枚举前两个,满足条件第三个自然是2019减去前两个。代码package lanqiao;public class TestMain1 { public static void main(String[] a
  • blog -求问题

    问题描述 给定一个int类型一维组 a[],一个int类型值 b。编写一个,判断组中有没有两个(a[i],a[j])等于b,如果存在,返回两个在a组中下表(return new int[]={1,2}
  • blog -快速排

    百科:快速排(Quicksort)是对冒泡排一种改进。 快速排由C. A. R. Hoare在1960年提出。它基本思想是:通过一趟排将要排分割成独立两部分,其中一部分所有都比另外一部分所有
  • blog -列求值

    问题描述思路: 斐波那契变体 考虑如果把20190324项每一项值都出来话,那么值范围就会超出基本类型能够表示范围,又考虑到题目是求最后四位,而加时前一位不会影响后一位果,例如
  • blog -快速排

    快速排--来自百度百科 首先设定一个分界值,通过该分界值将组分成左右两部分。  将大于或等于分界值集中到组右边,小于分界值集中到左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素
  • blog 十种排理解(前五)

    十种排理解(前五)1.冒泡排冒泡排是一种简单。它重复地走访过要排列,一次比较两个元素,如果它们错误就把它们交换过来。描述:比较相邻元素。如果第一个比第二个大,就交换它们两个;对每一对相邻元素作同样工作
  • blog -特别

    问题描述:思路:遍历1-n个,判断是否满足条件。代码:package club.test;public class TestMain11 { public static void main(String[] args) { int nu
  • ofc 为什么要学习

    为什么要学习
  • file 判断单链表是否有环以及求环入口环长度2种方案分析-附java代码

    <pre class="language-java"><code class="line-numbers data-output match-braces rainbow-braces">/**
  • blog -图着色问题

    -图着色问题问题描述: 图m-着色判定问题——给定无向连通图Gm种不同颜色。用这些颜色为图G各顶点着色,每个顶点着一种颜色,是否有一种着色使G中任意相邻2个顶点着不同颜色?个人感觉图着色问题类似与八皇后