4.前端算法3

2.13 索引是怎么实现的，倒排索引

参考答案：

倒排索引是目前搜索引擎公司对搜索引擎最常用的存储方式，也是搜索引擎的核心内容，在搜索引擎的实际应用中，有时需要按照关键字的某些值查找记录，所以是按照关键字建立索引，这个索引就被称为倒排索引。

首先你要明确，索引这东西，一般是用于提高查询效率的。举个最简单的例子，已知有5个文本文件，需要我们去查某个单词位于哪个文本文件中，最直观的做法就是挨个加载每个文本文件中的单词到内存中，然后用for循环遍历一遍数组，直到找到这个单词。这种做法就是正向索引的思路。

举一个例子，有两段文本

D1：Hello, conan!

D2：Hello, hattori!

第一步，找到所有的单词

Hello、conan、hattori

第二步，找到包含这些单词的文本位置

Hello（D1，D2）

conan（D1）

hattori（D2）

我们将单词作为Hash表的Key，将所在的文本位置作为Hash表的Value保存起来。

当我们要查询某个单词的所在位置时，只需要根据这张Hash表就可以迅速的找到目标文档。

结合之前的说的正向索引，不难发现。正向索引是通过文档去查找单词，反向索引则是通过单词去查找文档。

倒排索引的优点还包括在处理复杂的多关键字查询时，可在倒排表中先完成查询的并、交等逻辑运算，得到结果后再对记录进行存取，这样把对文档的查询转换为地址集合的运算，从而提高查找速度。

2.14 二叉树的实际应用场景

参考答案：

哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性，详见《信息论与编码》。
海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处，在处理大批量的动态的数据是比较有用。
C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。
B-Tree，B+-Tree在文件系统中的目录应用。
路由器中的路由搜索引擎。

2.15 数组和链表的优缺点

参考答案：

数组:存放内存地址必须连续的.
查找的时候很方便,可以通过数组下标获取数据;
添加删除很不方便,如果插入一个元素,必须这个元素后面的元素都往后移一个内存地址
删除,所有后面元素都往前移动一个内存地址

链表:存放内存地址可以不连续,存放方式是通过元素中的指针,来寻找下一个元素.
这种结构添加删除元素很容易,只要修改指针指向下下个元素,就能删除,而添加则是
一个元素的指针指向后面的插入位置后面的元素,插入位置的指针指向插入元素就行

比较

数组
优点:查询速度快,可随机访问
缺点:

删除插入效率低,
内存必须连续
有浪费内存的可能
数组大小固定,不能动态拓展

链表
优点:插入删除速度快,内存不需要连续,大小可以不固定
缺点:查询效率低,每次通过第一个开始遍历,只能顺序访问,不支持随机访问

2.16 1000w条数据如何排序，取前一百个

参考答案：

根据快速排序划分的思想
(1) 递归对所有数据分成[a,b）b（b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数
(2) 对(b,d]重复(1)操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分
(3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2）b2（b2,d2]两个区间，取（b2,d2]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。
先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。具体步骤如下：
step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为mO（lgm）=O(m lgm);
step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃
如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)O(lgm);
最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。
补充：这个方法的说法也可以更简化一些：
假设数组arr保存100个数字，首先取前100个数字放入数组arr，对于第101个数字k，如果k大于arr中的最小数，则用k替换最小数，对剩下的数字都进行这种处理。
分块查找

先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较

2.17 AST 抽象语法树

参考答案：

抽象语法树（abstract syntax code，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，这所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节，比如说，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法，也就是说语法分析阶段所采用的上下文无文文法，因为在写文法时，经常会对文法进行等价的转换（消除左递归，回溯，二义性等），这样会给文法分析引入一些多余的成分，对后续阶段造成不利影响，甚至会使合个阶段变得混乱。因些，很多编译器经常要独立地构造语法分析树，为前端，后端建立一个清晰的接口。

抽象语法树在很多领域有广泛的应用，比如浏览器，智能编辑器，编译器。

2.18 算法：一个小偷要偷一排顺序的房子，每个房子有固定的价值，但小偷不能偷连续的房子，问小偷能偷到的最大价值

参考答案：

示例 1:

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

问题求解题意简单说来就是不能偷相邻的两个房屋, 而且要尽量偷得多. 这是典型的动态规划问题, 思路如下, 由于后面房间能偷到的最大钱数取决于前面房间能偷到的最大钱数, 所以可以从第一间房子向后看. 建立一个数组dp, 数组中的第n个元素保存前n间房屋总共能偷到的最大钱数:

若只有一间房子, 则只能偷这间, 则前1间房屋能偷到的最大金额一已知, 保存下来;
若有两间, 则偷其中最多的, 则前两间房屋能偷到的最大金额已知, 保存下来;
若有3间, 则分为两种情况, 1)偷房屋 1和3; 2) 只偷房屋2. 比较这两种哪种获益大. 这可以抽象成两个子问题, 决定这两个子问题的关键是第三间房子偷与否. 分别把偷(子问题1)和不偷(子问题2) 的结果计算出来, 选出最大就是了. 现在, 前三间能偷到的最大金额已知, 保存下来, 以供偷第4、5...N 间房子时参考.
若有4间, 则又是两种情况: 1)偷4不偷3; 2)不偷4. 这两种情况只和前三间房屋偷到的金额(dp[3])和前两间房屋偷到的金额(dp[2])的结果有关,把这两种情况下的金额计算出来, 选择最大的就可以了, 即 max(房屋4的钱+dp[2], dp[3]);
由此可得, 第n间房屋偷还是不偷只要考虑 dp 数组中的dp[n-1]和dp[n-2]+当前可得的金额这两个因素就可以了.

所以状态方程为:max(dp[n-2] + thisValue, dp[n-1]), 代码为:

var rob = function(nums) {
    // 判断异常
    if(!nums || nums.length === 0){ 
        return 0;
    }
    // 边界条件
    if(nums.length < 3){
        return Math.max(...nums);
    }
    // 状态方程 dp(i) = max( dp(i-1) , dp(2) + arr[i])
    let dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for(let i = 2; i < nums.length; i++){
        dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[dp.length-1];
};