招行面试题--求无序数组最长连续序列的长度，这里连续指的是值连续--间隔为1，并不是数值的位置连续
给出一个未排序的整数数组，找出最长的连续元素序列的长度。 最长的连续元素序列是[1, 2, 3, 4]。返回它的长度：4。 你的算法必须有O(n)的时间复杂度 。
1.比较器的写法；防止0的出现
1.普通解法：利用两个hashset a和b a用于记录，b用于产生结果。从第十位字符开始向后遍历整个字符串，判断长度为10的字符串是否在a出现过，没有则加入hashset a，有的话则加入结果hashset b。
结果集一定要用hashset，不能用链表，用链表会出现重复。
00,01,10,11分别代表'A','C','G','T'，可以用20个bit位来代表长度为10的子字符串。相当于将字符串重新编码了。可以减少substring的调用次数，加快效率。
1. 没有想到优化的方法。
解法：分层遍历，每次取最右边的那个节点
解法：将出现过的位置变为负的
2.再次遍历，将不为负数的位置加入list中
解法：仔细观察可以发现规律，最后的结果是所有数字的最左边的共同部分
比如来看一个范围[26, 30]，它们的二进制如下：
左边的共同部分是11，所以最后结果是11000
所以先将m和n向右移，直到m和n相等，假设右移了i位，则最后结果为m<<i.
1.没有想出最好的解法
首先遍历所有节点，将其邻居的入度加一 ，当某一个节点加入拓扑排序后，将其所有邻居的入度减一
有向图是无法从一个节点找到所有节点的，所以这里给出的参数是节点的列表，无向图只要是连通的就可以由一个节点找到所有节点
解法：可以根据上一题lintcode 127 Topological Sorting来求解，只不过要在拓扑排序之后判断图中是否存在环，若存在环，则返回false，反之返回true。
回顾一下图的三种表示方式：边表示法（即题目中表示方法），邻接表法，邻接矩阵。我们要用邻接表来表示图，来实现拓扑排序，找出最后是否存在入度不为0的节点，若存在则有环。
1. 忘了拓扑排序是怎么回事了。
解法：所求即为拓扑排序的逆序。注意当变列表为空的时候，也就是每门课程都没有依赖课程，这时候返回的是任意顺序就行了。
//入度为0的先加入队列中
//构建拓扑排序的逆序，即题目要求的结果
1.用数组实现（递归），比较简单而且更优化 wordEnd = true表示一个单词的结束。当一个单词结束时，这条边对应的子节点wordEnd = true
2.用数组实现（非递归），比递归更加优化
3.第三次做了，还是出现了bug，下次用非递归实现。将wordEnd的位置放错，我放在了父节点上，应该放在子节点上。也就是说当一个单词结束时，这条边对应的子节点wordEnd = true
题意：也就是trie树的一个应用
解法：插入与之前trie树的一样了，用的是非递归的方法。查找的话如果遇到了'.'，就需要遍历每一棵子树
优化：将额外空间优化为常数级。mod 2的做法，这个方法很通用，一定要记住。
2.一年前做的，现在果然就不会了。动态规划的做法
解法：结合robI使用动态规划。
因为第一位和最后一位也是邻居，所以第一位和最后一位不能同时抢劫。可以分两种情况：
1.抢劫的范围是从第一位到倒数第二位
2.抢劫的范围是从第二位到最后一位
去这两种情况的较大值，也就是最后的结果。这两种情况也就是跟robI一样的情况了，只是数组的开始结束位置做了改变，稍微改变一下robI的代码就可以了。
//这就是robI的解法了
1.第一次做，没想出来
解法：对每一个节点有两种选择，偷或者不偷。递归向下，now[0]表示当前根节点不偷，now[1]表示当前根节点偷
1。没有想出来，其实九章给出的两种答案是一种解法。
1.最优解法二分法。以数据范围作为二分的空间。每次去计算矩阵中小于等于中位数的数的个数。
若个数小于k，则start = mid+ 1（也即是所求肯定大于中位数）；反之，end = mid - 1，同时记录可能的ans = mid（也就是说ans最大可能等于mid，再去mid-1之前去找，若找到则更新），最后返回ans。
时间复杂度为nlog(x) ,n为矩阵元素个数，x为最大值与最小值的差值
2.次优解法：优先队列。
a.先将第一行的每个元素加入优先队列（或者第一列）
b.执行k-1次：将队头元素poll出来，并且offer进去这个元素的同一列的下一行（上一步若是第一列，则是同一行的下一列）。
c.上一步需要位置信息，所以可以自定义一个类，并且实现优先队列的比较器。
实际上这个过程是poll了最小的k-1个数出来，那么第k个数就是下一个队头元素了。时间复杂度为klog(col),col为行数（klog(row),row为行数），第一步是选择第一行还是第一列可以比较一下选择较小值。
解法：优先队列。与上一题378相似的解法。
解法：1.优先队列 时间复杂度为O(n)logk
2.更加优化的quick select 快速选择算法 ，将quicksort修改一下，每次只查找左右两部分的其中一个。平均时间复杂度能到O(n),最坏时间复杂度为O(n^2)。
在start~end的数组范围内找第k大的数。
如果大于等于轴元素的个数大于等于k个，那就去右半边找第k大的，反之，去左半边找第k - (end - left + 1)大的
注意left和right相差一位和两位是不同的情况
1.获得树的高度h（高度从0开始计数），只要不断的往左子树递归就可以了。空节点返回-1；
2.判断右子树的高度是否 为当前根节点高度减一 （h - 1）：
a.如果是的。说明最后一层的最后一个节点在右子树上。所以将总结点数加上左子树（左子树h-1层）的节点数目 (2^h) - 1 + 1(加一是根节点),将当前节点置为右子树根节点。
b.如果不是。说明最后一层的最后一个节点在左子树上。所以将总结点数加上右子树（右子树h-2层）的节点数目 (2^(h-1)) - 1 + 1(加一是根节点),将当前节点置为左子树根节点。
1.遍历的做法是tle的，记住树的节点数的计算方法，高度从0开始，高度为h的层，节点数为2^h,前h层节点数为2^(h + 1) - 1。.
