数据结构和算法作为程序员的基本功，一定得稳扎稳打的学习，我们常见的框架底层就是各类数据结构，例如跳表之于redis、B+树之于mysql、倒排索引之于ES，熟悉了底层数据结构，对框架有了更深层次的理解，在后续程序设计过程中就更能得心应手。掌握常见数据结构和算法的重要性显而易见，本文主要讲解了几种常见的数据结构及基础的排序和查找算法，最后对高频算法笔试面试题做了总结。本文会持续补充，希望对大家日常学习或找工作有所帮忙。
1、什么是数据结构？(研究应用程序中数据之间逻辑关系、存储方式及其操作的学问就是数据结构)
- 程序中数据大致有四种基本逻辑结构：集合(同属一个集合)/线性关系(一对一)/树形结构(一对多)/图状结构或网状结构(多对多)
- 物理存储结构：顺序存储结构/非顺序结构(链式存储/散列结构)
-
算法的设计取决于逻辑结构；算法的实现依赖于存储结构
2、为什么学习数据结构和算法？
有3点比较重要 (王争)
- 1、直接好处是能够有写出性能更优的代码；数据结构：存储；算法：计算；
- 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算。
- 2、算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面；
- 3、长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一。
《大话数据结构 程杰》入门
《数据结构与算法分析：Java语言描述》(大学课本 伪代码)
《剑指offer》 使用的C++语言来实现的，现在我不怎么使用了
《程序员代码面试指南:IT名企算法与数据结构题目最优解》左程云，现在正在看的书
《编程珠玑》(对大数据量处理的算法)
《编程之美》(超级难)
《算法导论》(很厚很无聊)
《算法第四版》(推荐 本书没有动态规划)
《数据结构与算法 极客时间》 王争google
《算法之美》(闲暇阅读) 是短网址服务的域名）
7、编程实现一个LRU缓存淘汰算法 (使用散列表+链表组合实现缓存淘汰算法)LinkedHashMap(思路牛逼)(双向链表+散列表)(使用双向链表支持按照插入的顺序遍历数据，支持按照访问顺序遍历数据)
一个缓存（cache）系统主要包含下面这几个操作：往缓存中添加一个数据；从缓存中删除一个数据；在缓存中查找一个数据。
①使用双向链表存储数据，链表中每个节点存储数据（data）、前驱指针（prev）、后继指针（next）和hnext指针（解决散列冲突的链表指针）。
②散列表通过链表法解决散列冲突，所以每个节点都会在两条链中。一条链是双向链表，另一条链是散列表中的拉链。前驱和后继指针是为了将节点串在双向链表中，hnext指针是为了将节点串在散列表的拉链中。(牛逼)
- 往缓存中查找一个数据：在散列表中查找数据的时间复杂度为O(1)，找到后，将其移动到双向链表的尾部
- 删除数据：在O(1)时间复杂度里找到要删除的结点，双向链表可以通过前驱指针O(1)时间复杂度获取前驱结点
- 添加一个数据：先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。
java中有现成的工具可以使用
- LinkedHashMap维护了插入的先后顺序【FIFO】，适合LRU算法做缓存（最近最少使用）(在项目中被用到过)
11、字符串处理算法总结：
理解常用字符串匹配算法的原理、实现、设计意图和应用场景，搞清楚能解决什么问题。
思路：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了，效率取决于哈希算法的设计方法。
算法思想：编程中一定会出现的问题：变种非常多(反转/反转单词/子串/最长子串/最长子序列)
- 1、用固定支付替换字符串中的空格
只考虑字母和数字字符，先用isletterOrDigit来跳过其他字符，第一个字符与最后一个字符依次比较，然后I++，J–
- 3、数组的最长公共前缀
先用数组的sort方法升序排列，找出数组第一个字符串和最后一个的长度，按小的计算，比较字符串的元素，若相等就
- 4、最长回文串 区分大小写
字符出现次数为双+一个只出现一次的字符，遍历数组，字符在hashset中就移除，count++，否则，添加进去
5、反转字符串，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题 输入：[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]
7、字符串转换整数 请你来实现一个 atoi 函数，使其能将字符串转换成整数
该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数
例如：输入: " -42" 输出: -42 第一个非空白字符为 ‘-’, 它是一个负号
输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字
12.1、如何遍历一棵二叉树？
二叉树是n个有限元素的集合，由根元素以及左右子数组成。集合可以为空。
- 概念：结点的度，结点所拥有的子树的个数称为度。
叶节点，度为o的结点。
分支节点，即非叶子结点
- 路径：n1，n2，，，nk的长度为路径
- 层数：根结点层数为1，其余的结点++双亲
- 满二叉树：所有叶子结点在同一层
- 完全二叉树：叶子结点只能出现在最下层和次下层。
- 性质： 非空二叉树第i层最多2{i-1}个结点
深度为k，最多2{k}-1个结点，最少k个结点
非空二叉树，度为0的节点数比度为2的节点数多1，n0=n2+1；
n个结点的完全二叉树的深度为lgn+1
- 存储：1、基于指针或者应用的二叉链式存储法；2、基于数组的顺序存储法(适合完全二叉树)
链式存储法：每个结点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针
顺序存储法：节点X存储在数据中下标为i的位置，下标为2i的位置存储的是左子节点，下标为2i+1的位置存储的是右子节点。
- 遍历：使用队列来实现对二叉树的层序遍历，思路：根结点放入队列，每次从队列中取出一个结点，打印值。若这个值有子结点，子结点入队尾，直至队列为空。 代码P305（是一种广度优先的遍历算法）
递归实现：中序遍历，先序遍历，后序遍历(表示的是节点与它的左右子树节点遍历打印的先后顺序) 时间复杂度O(n)
非递归中序遍历：首先要移动到结点的左子树，完成左子树的遍历后，再将结点出栈进行
非递归先序遍历：需要使用一个栈来记录当前节点，以便在完成左子树遍历后能返回到右子树中进行遍历；
* 在遍历左子树之前，把当前节点保存在栈中，直至遍历完左子树，将该元素出栈，然后找到右子树进行遍历。
12.2、二叉查找树(二叉搜索树)(Mysql索引的底层)
二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作
1、查找操作：我们先去根节点，如果它等于我们要查找的数据，就返回；如果比根节点小，就在左子树中递归查找；如果比根节点值大，就在右子树中递归查找。
2、插入操作 得先比较，从根节点开始
3、二叉查找树的删除操作(1、如果要删除的节点没有子节点，我们只需要直接将父节点中指向要删除节点的指针置为null；2、要删除的节点有一个子节点，我们只需要更新父节点，指向要删除节点的指针
3、要删除的节点有两个子节点，找到这个节点的右子树中的最小节点，替换到要删除的节点上)
二叉查找树的执行效率：若是根节点的左右子树季度不平衡，已经退化到了链表，查找的时间复杂度为O(n)；平衡二叉查找树的时间复杂度O(lgn)
12.3、红黑树的应用场景(TreeMap 红黑树：一种近似平衡的二叉查找树：二叉树中任意一个节点的左右子树的高度相差不能大于1。包括完全二叉树、满二叉树) 红黑树一定得掌握
-
红黑树是于1972年发明的，当时称为对称二叉B树，1978年得到优化，正式命名为红黑树。它的主要特征是在每个节点上增加一个属性来表示节点的颜色，可以是红色，也可以是黑色。红黑树和 AVL 树类似，都是在进行插入和删除元素时，通过特定的旋转来保持自身平衡的， 从而获得较高的查找性能。与AVL树相比，红黑树并不追求所有递归子树的高度差不超过1，
而是保证从根节点到叶子节点的最长路径不超过最短路径的2 倍，所以它的最坏运行时间也是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除操作后的自平衡调整。当然 ， 红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件，如下
-
1、每个节点要么是红色，要么是黑色;
2、根节点必须是黑色;
3、红色节点不能连续(红色节点的孩子和父亲都不能是红色);
4、对于每个节点，从该点至叶子的任何路径，都含有相同个数的黑色节点;
5、确保节点的左右子树的高度差，不会超过二者中较低那个的一倍;
-
应用场景：搜索，插入删除次数多(为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的)
1、map和set都是用红黑树实现的
3、epoll在内核中的实现，用红黑树管理事件块
AVL树适合用于插入删除次数比较少，但查找多的情况
-
关于动态数据结构：链表/栈/队列/哈希表（链表适合遍历的场景，插入和删除操作方便；栈和队列可以算一种特殊的链表，分别使用先进后出和先进先出的场景；哈希表适合插入和删除比较少，查找比较多的场景；红黑树对数据要求有序，对数据增删改查都有一定要求的时候）
-
散列表/跳表/红黑树性能对比：
1、散列表：插入删除查找都是O(1)，是最常用的，缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于不需要顺序遍历、数据更新不那么频繁的；
2、跳表：插入删除查找都是O(lgn)，能顺序遍历，缺点是空间复杂度O(n)，适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便；
3、红黑树：插入删除查找都是O(lgn)，中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。
12.4、数据结构 堆
- 满足条件：1、堆是一个完全二叉树；2、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
堆都支持哪些操作以及如何存储一个堆(通过数组来存储)
- 缺点：对于一组已经有序的数据来说，经过建堆后，数据反而变得更无序了
- 堆排序的过程：1、建立初始堆(把数组中的元素的序列看成是一颗完全二叉树，对该二叉树进行调整，使之成为堆) 根节点的索引是1
2、堆排序(把根元素与最右子节点交换，然后再次构建堆，再与倒数第二集结点交换，然后再构建堆) 生成由小到大排列的数组
时间复杂度：假设有n个数据，需要进行n-1次建堆，每次建堆本身耗时lgn，则其时间效率为O(nlgn) 空间复杂度O(1)
排序操作： //n表示数据的个数，数组a中的数据从下标1到n的位置。
为什么快速排序要比堆排序性能好？
1、堆排序数据访问的方式没有快速排序友好(开拍是顺序访问；堆排序是跳着访问，对cpu缓存不友好)
2、同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
应用：1、优先级队列；2、topK；3、流里面的中位数；
12.5、AC自动机：如何用多模式串匹配实现敏感词过滤功能？(使用Trie树)
字符串匹配算法：单模式串匹配算法(BF算法、RK算法、BM算法、KMP算法)，多模式串匹配算法(Trie树 最长前缀匹配)
AC自动机算法包含两个部分，第一部分是将多个模式串构建成AC自动机，第二部分是在AC自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成Trie树，另一个是在Trie树上构建失败指针
BF(直接匹配算法 简单场景，主串和模式串都不太长, O(mn) 效率最低)
KP(字符集范围不要太大且模式串不要太长，否则hash值可能冲突，O(n))
naive-BM(模式串最好不要太长（因为预处理较重）,比如IDE编辑器里的查找场景；预处理O(mm),匹配O(n),实现较复杂，需要较多额外空间)
KMP(适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快)
还有一种比BM/KMP更快，且实现+理解起来都更容易的Sunday算法 naive-Trie(适合多模式串公共前缀较多的匹配(O(n*k)) 或者 根据公共前缀进行查找(O(k))的场景，比如搜索框的自动补全提示 root不存储字符)
AC自动机(适合大量文本中多模式串的精确匹配查找, 查找的复杂度可以到O(n))**
定义：AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上
一个是数据的保存位置，
- B树的数据每个节点既保存索引，又保存数据；B+树的数据只会落在叶子节点
上述两种特性造成的现象为：
1、B+树查询时间复杂度固定是logn，B树查询复杂度最好是 O(1)。
2、B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B树每个节点 key 和 data 在一起，无法区间查找。
3、B+树更适合外部存储，也就是磁盘存储。由于父级节点无 data 域，每个节点能索引的范围更大更精确
4、注意这个区别相当重要，B树每个节点即保存数据又保存索引，所以磁盘IO的次数很少，B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。
- MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据。比如之前我们的表可能有用户表、订单表、购物车表等等，还要建立他们之间的外键关联关系。但是类Json就不一样了。
- MongoDB使用B树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。
- Mysql作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。
13、海量数据的处理思路问题
13.1、大数据量的问题：
10w个id，怎么去100亿个id里找数据，怎么做能更快，分库分表？
13.2、有10G大小的文件，每行记录一条运单信息，机器大小是500M，求出出现次数最多的前1000条运单号，给出思路。
典型的Top K算法(分治思想)
1、先对这批海量数据预处理，在O(N)的时间内用Hash表完成分组(相同单号被分配到Hash桶中的同一条链表中) %20 20个文件，每个文件500M 堆的大小取决于机器的内存值500M;
2、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK
3、对每个堆中的TOPk，计算出前k个数（归并排序）
13.3、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
方案1：可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M
遍历文件b，采取和a相同的hash函数将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，
不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
13.4、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
方案1：用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。
然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素
13.5、怎么在海量数据中找出重复次数最多的一个？
方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求100w个数中找出最大的100个数
用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)
13.6、如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？
13.7、假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
13.8、假设我们有1000万个整型数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这1000万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过100MB，你会怎么做呢？
13.9、如何在海量数据中快速查找某个数据？(索引)(在计算机组成中称为寻址)
MySQL底层依赖的是B+树这种数据结构，Redis这样的Key-Value数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？
- 索引存储位置：在内存还是硬盘
- 单值查找还是区间查找？
单关键词查找还是多关键词组合查找？对于结构化数据的查询需求(MYSQL)，针对多个关键词的组合，建立索引；对于非结构数据的查询需求(搜索引擎)，以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。
- 构建索引常用的数据结构？
对动态数据建立索引：散列表、红黑树、跳表、B+树；位图、布隆过滤器可以作为辅助索引；有序数组可以用来对静态数据构建索引。
- 散列表：一些键值数据库，比如Redis、Memcache，就是使用散列表来构建索引的，增删改查的性能非常好，时间复杂度为O(1)，这类索引，一般都构建在内存中；
- 红黑树：作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也非常适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，使用的是红黑树；
- B+树：比起红黑树来说，更加适合构建存储在磁盘中的索引，B+树是一个多叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，
读取B+树索引，需要的磁盘IO次数非常更少，关系型数据库的索引：如Mysql、oracle，使用的是B+树建立索引
- 跳表：支持快速添加、删除、查找数据。而且通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的
布隆过滤器：对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。内存占用非常少
有序数组：如果数据是静态的，也就是不会有插入、删除、更新操作，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据
- 你知道基础系统、中间件、开源软件等系统中，有哪些用到了索引吗？这些系统的索引是如何实现的呢？
1、区块链拿以太坊来说，存储用的leveldb，数据存储用的数据结构是帕特利夏树，是一种高级的trie树，很好的做了数据的压缩；
2、消息中间件像kafka这种，会去做持久化，每个partition都会有很多数据，会有大量数据存储在磁盘中，所以每个partition也会有个索引，方便去做快速访问。
3、ES中的倒排索引用了trie树(一种专门处理字符串匹配的数据结构),对每个需要索引的key维护了一个trie树,用于定位到这个key在文件中的位置,然后直接用有序列表直接去访问对应的documents
trie树(两个操作：一个将字符串插入到Trie树的过程。另一个是在Trie树中查询一个字符串)
Q:Trie树：如何实现搜索引擎的搜索关键词提示功能？(为了方便快速输入，当你在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示)
A:‘字典树’。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题.
Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起（感觉有点像霍夫曼编码：左0右1）
时间复杂度：O(k) k为字符串长度
应用场景：自动输入补全，比如输入法自动补全功能、IDE代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等
Q:Trie树应用场合对数据要求比较苛刻，比如字符串的字符集不能太大，前缀重合比较多等。如果现在给你一个很大的字符串集合，比如包含1万条记录，如何
通过编程量化分析这组字符串集合是否比较适合用Trie树解决呢？也就是如何统计字符串的字符集大小，以及前缀重合的程度呢？
A:依次读取每个字符串的字符构建 Trie 树，用散列表来存储每一个节点。每一层树的所有散列表的元素用一个链表串联起来，求某一长度的前缀重合，在对应树层级上遍历该层链表，
求链表长度，除以字符集大小，值越小前缀重合率越高。遍历所有树层级的链表，存入散列表，最后散列表包含元素的个数，就代表字符集的大小
如何存储一个Trie树？
13.10、并行计算：利用并行处理提高算法的执行效率(分治的思想)
算法无法再继续优化的情况下，如何来进一步提高执行效率呢？可以使用一种简单但好用的优化方法，那就是并行计算。
- 1、并行排序 对时间复杂度为O(nlgn)的三种排序算法：归并/快排/堆排进行并行化处理
如：归并排序时，将8G的数据先划分为16个小的数据集合，然后多线程处理，最后将这16个有序集合合并；快速排序中，先扫描一遍数据，遭到数据所处的范围区间，
同样划分为16个小区间，并行进行排序，等到16个线程都执行借宿之后，得到的数据就是有序数据了。
- 2、并行查找 散列表，给动态数据构建索引，在数据不断加入的时候，散列表的装载因子就会越来越大。为了保证散列表性能不下降，我们就需要对散列表进行动态扩容，
可以将数据随机分割成k份（比如16份），每份中的数据只有原来的1/k，然后我们针对这k个小数据集合分别构建散列表，增加存储空间的利用率。
14.1、如何存储微博、微信等社交网络中的好友关系？
-
微博：有向图(入度代表粉丝数，出度代表关注数)
社交关系存储方法：邻接表(存储用户关注关系)+逆邻接表(存储被关注信息)
-
需求：判断用户A是否关注了用户B；判断用户A是否是用户B的粉丝；用户A关注用户B；用户A取消关注用户B；
根据用户名称的首字母排序，分页获取用户的粉丝列表；根据用户名称的首字母排序，分页获取用户的关注列表。
-
如何迅速判断俩用户之间的关注关系？
因为需要按首字母排序，获取粉丝列表或关注列表，在邻接表右边使用跳表是最合适的(跳表存储的数据有序)。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是O(logn)，空间复杂度上稍高，是O(n)
如何解决数据量大的问题？
可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。例如：在机器1上存储顶点1，2，3的邻接表，在机器2上，存储顶点4，5的邻接表，当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。
-
微信：无向图(好友间建立一条边)
-
QQ：带权图(每条边都有一个权重，可以通过权重表示QQ好友间的亲密度)
14.2、如何在内存中存储图这种数据结构？
- 邻接矩阵：依赖一个二维数组，A[i][j]=w表示可达，w表示权重 (我们的扫雷游戏就是使用的这种有向图数据结构，带权值(0表示没有操作，1表示地雷，-1表示插上了红旗)下次可以做成PPT
缺点：对于无向图来说，浪费了一半的空间；对于稀疏矩阵，绝大多数的存储空间都被浪费了
优点：基于矩阵，在获取两顶点的关系时，就非常高效；第二是方便计算，如求最短路径
- 邻接表：每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
缺点：在邻接表中查询两个顶点间的关系效率较低，改进措施(邻接表右侧的链表可以使用二叉树/红黑树/跳表来表示，跳表最适合)
14.3、图的其他领域应用？
Gradle这个编译工具，内部组织task的方式用的是有向图；
互联网上网页之间通过超链接连接成一张有向图；
城市乃至全国交通网络是一张加权图；
14.4、如何找出社交网络中的三度好友关系？(深度优先和广度优先搜索算法)(存储使用邻接表)(无向图)
- BFS:广度优先搜索：时间复杂度O(V+E) V为顶点个数，E为边的个数(对于一个连通图来说,E肯定要大于等于V-1，所以，广度优先搜索的时间复杂度也可以简写为O(E)。)
广度优先搜索的空间消耗主要在几个辅助变量visited数组、queue队列、prev数组上.所以空间复杂度是O(V)。
- DFS:深度优先搜索(深度优先搜索找出来的路径，并不是顶点s到顶点t的最短路径) 时间复杂度是O(E) 空间复杂度是O(V)
借助 栈来实现 辅助变量visited数组和prev数组
- 社交网络中的三度好友关系?
非常适合于图的广度优先搜索算法来解决，因为它是层层往外推进的。首先，遍历与起始顶点最近的一层顶点，也就是用户的一度好友，然后再遍历与用户距离的边数为2的顶点，也就是二度好友关系，以及与用户距离的边数为3的顶点，也就是三度好友关系。
适用场合：状态空间不大，也就是图不大的搜索，属于基本的搜索算法(高级搜搜算法有A*/IDA*)
14.5、如何确定代码源文件的编译依赖关系？(拓扑排序 有向无环图)
问题阐述：一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp依赖B.cpp，那在编译的时候，编译器需要先编译B.cpp，才能编译A.cpp。我们可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。
两种实现方式：Kahn和DFS
1、Kahn基于贪心算法，思路是如果s需要先于t执行，那就添加一条s指向t的边，如果某个顶点入度为0， 也就表示，没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行。
我们先从图中，找出一个入度为0的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减1）
我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。
3、拓扑排序的应用：需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。
实现拓扑排序的Kahn算法能检测图中环的存在，若果最后输出的顶点个数少于图中顶点个数，说明图中还有入度不是0的顶点，那就说明，图中存在环。
这就是环的检测问题：(只需要记录已经访问过的用户ID，当用户ID第二次被访问的时候，就说明存在环)
如果想知道数据库中所有用户之间的推荐关系，有没有存在环的情况，需要使用拓扑排序算法，我们把用户之间的推荐关系，从数据库中加载到内存中，然后构建成有向图的数据结构，再利用拓扑排序，就可以快速检测出是否存在环。
建模：将地图抽象成具体的数据结构-图，把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。
最短路径算法实现Dijkstra 时间复杂度是O(E*logV) E为所有边的个数，V表示顶点的个数
思想：1、采用贪婪法：总是选取最接近源点的顶点；2、使用优先队列并按照到s的距离来存储未被访问过的顶点；3、不能用于权值为负的情况。
具体而言：Dijkstra通过回溯穷举所有从s到达t的不同路径，在此基础上，利用动态规划的思想，对回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索，能得到最优解。
实际的应用中，相比Dijkstra算法，地图软件更多的是A*启发式搜索算法
-
实例2：在计算最短时间的出行路线中，如何获得通过某条路的时间呢？
与时间相关的变量：1、路径长度；2、路况；3、拥堵情况；4、红绿灯个数，获取这些因素后就可以建立一个回归模型(如线性回归)来评估时间
情况3是数据是动态的，可以通过与交通部门合作获得路段拥堵情况，联合其他导航软件获得该路段的在线人数
-
实例3：今天讲的出行路线问题，我假设的是开车出行，那如果是公交出行呢？如果混合地铁、公交、步行，又该如何规划路线呢？
混合公交、地铁和步行时，地铁时刻表是固定的，容易估算。公交虽然没那么准时，大致时间是可以估计的，步行时间受路拥堵状况小，基本与道路长度成正比，也容易估算。总之，公交、地铁、步行，时间估算会比开车更容易，也更准确些。
-
实例4：翻译系统。只能针对单个词来做翻译。如果要翻译一整个句子，我们需要将句子拆成一个一个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回一组可选的翻译列表，并且针对每个翻译打一个分，表示这个翻译的可信程度。我们希望计算出得分最高的前K个翻译结果。
解答：使用Dijkstra最短路径算法
14.7、A*搜索算法(实现游戏中的寻路功能)
与Dijkstra算法的三点区别：
1、优先级队列构建的方式不同。A算法是根据f值（也就是刚刚讲到的f(i)=g(i)+h(i)）来构建优先级队列，而Dijkstra算法是根据dist值（也就是刚刚讲到的g(i)）来构建优先级队列；
2、A算法在更新顶点dist值的时候，会同步更新f值；
3、循环结束的条件也不一样。Dijkstra算法是在终点出队列的时候才结束，A算法是一旦遍历到终点就结束。
(A每次从f值最小的顶点出队列，一旦搜索到重点就不再继续考察其他顶点和路线，也就不可能找出最短路径)
总结：A算法属于一种启发式搜索算法，还有一些其他的同类型算法：IDA算法、蚁群算法、模拟退火算法等
启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进，这种算法找出的路线，并不是最短路线，但是启发式搜索算法能很好地平衡路线质量和执行效率，
它在实际的软件开发中的应用更加广泛。
补充1：break的作用域
break 跳出最近的｛｝包裹的代码，如果有标记，就跳出标记的｛｝
- 利用欧几里得公式计算俩用户听歌喜好的距离
- 头条的新闻推送，淘宝的猜你喜欢
好处：如果用散列表存储着1千万的数据，数据时32位的整型数，也就是需要4字节的存储空间，那总共至少需要40MB的存储空间，如果我们通过位图的话，数字范围在1到1亿之间，
只需要1亿个二进制位，也就是12MB左右的存储空间即可。
15.1、什么是布隆过滤器，其实现原理是？（java.util的BitSet类，实现类位图） False positive指的是？（蚂蚁问到）
布隆过滤器是由一个很长的二进制向量(位图)加一系列随机映射函数(例如hash函数)组成。它可以用于检索一个元素是否在一个集合中。
例如：我们把hash函数设计成f(x)=x%n,其中，x表示数字，n表示位图的大小(1亿)，也就是，对数字跟位图的大小进行取模求余。
hash函数的特殊设计：一个hash函数可能会存在冲突，那使用多个hash函数一块儿定义一个数据，我们把这K个数字作为位图中的下标，降低冲突的概率。当要查询某个数字是否存在的时候，我们用同样的K个哈希函数，对这个数字求哈希值，如果都是true，则说明，这个数字存在。(带来了新的缺点：容易误判)优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误判(即判断一个元素存在，可能被误判，而判断这个元素不存在，则一定不存在)和删除困难
数据结构采用了bitmap 位图 解决缓存击穿的问题，有一个拦截机制，能迅速判断请求是否有效，他的内部维护了一系列合法有效的key，若是请求的元素在这个集合当中，说明请求有效。
布隆过滤器有一定的误检率，即判断一个元素存在，可能被误判(例如布隆过滤器中只存在A和E，但是对B进行过滤时，刚好被定位到了A的上半部分和E的下半部分，被误判为存在)
1、ip地址的布隆过滤器(比如统计一个大型网站的每天的UV数) 网页爬虫的url去重
3、比特币(spv客户端访问full比特币客户端时，使用布隆过滤器进行拦截，减轻系统负担)
4、分布式系统MapReduce中，使用布隆过滤器判断某个子任务是否存在某台机器上
例子1：我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有10亿，那我们可以用一个10倍大小的位图来存储，也就是100亿个二进制位，换算成字节，
那就是大约1.2GB。之前我们用散列表判重，需要至少100GB的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。
例子2：假设我们有1亿个整数，数据范围是从1到10亿，如何快速并且省内存地给这1亿个数据从小到大排序？
传统的做法：1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)
使用位图算法：数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N
15.2、概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？
- 1.基于黑名单的过滤器
①布隆过滤器:如果我们要存储500万个手机号码，我们把位图大小设置为10倍数据大小，也就是5000万，那也只需要使用5000万个二进制位（5000万bits），换算成字节，
也就是不到7MB的存储空间。比起散列表的解决方案，内存的消耗减少了很多。
②我们可以把黑名单存储在服务器端上，把过滤和拦截的核心工作，交给服务器端来做。手机端只负责将要检查的号码发送给服务器端，服务器端通过查黑名单，
判断这个号码是否应该被拦截，并将结果返回给手机端。网络传输的速度较慢(硬性要求：必须联网处理)
前提：有大量的样本数据（比如1000万条短信），并且每条短信都做好了标记，它是垃圾短信还是非垃圾短信
- 3.基于概率统计的过滤器
解决了基于规则的过滤器容易被绕过的缺陷。基于概率统计的基础理论是朴素贝叶斯算法(将一个未知概率的求解，分解成其他三个已知概率的求解)
- 总结：可以结合上述3点共同判断一条短信是否为垃圾短信
评论中的观点：机器学习尤其是NLP方向的很多算法可用于anti-spam(反垃圾邮件)，判别式模型(logistic regression)效果通常好于生成式模式(naive-bayes),对于电话号码数字，正则或定时拉黑名单比ML模型简单可靠。
原则：找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你
1.基于相似用户做推荐(基于用户建模的协同过滤算法推荐)
计算多维向量(用户对各首歌曲的喜爱程度作为向量)之间的距离，使用欧几里得计算公式
2.基于相似歌曲做推荐
针对每首歌曲，将每个用户的打分作为向量
1、稀疏性问题：当用户评价项目数少于中项目数时，就很容易造成评价矩阵相当稀疏，导致算法难以找到一个用户的偏好相似邻居。
2、冷启动问题：基于用户协同过滤是建立在有大量用户对某个产品的评价上的，由于在新产品开始阶段没有人购买，也没有对其进行评价，那么在开始阶段也将无法对其进行推荐
3、算法扩展性问题。随着物品数尤其是用户数的剧烈增加，最近邻居算法的计算量也相应增加，所以不太适合数据量大的情况使用，所以推荐系统性能也会大大受影响
16、断点续传思路和算法
在http头文件里面保存了content和content-type标签，用于记录传输文件的字节段。
