招行面试题--求无序数组最长连续序列的长度,这里连续指的是值连续--间隔为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。.