面试思考题:最多连续数的子集;及单链表和之恋分析

2013-06-30

给一个整数数组, 找到其中包含最多连续数的子集,比如给:15, 7, 12, 6, 14, 13, 9, 11,则返回: 5:[11, 12, 13, 14, 15] 。最简单的方法是sort然后scan一遍,但是要o(nlgn). 有什么O(n)的方法吗?


==============

单链表和之恋分析:


原题:两个单链表(singly linked list),每一个节点里面一个0-9的数字,输入就相当于两个大数了。然后返回这两个数的和(一个新list)。这两个输入的list长度相等。 要求是:1. 不用递归。2. 要求算法在最好的情况下,只遍历两个list一次 ,最差的情况下两遍。


分析:遇到一个面试题,首先,要澄清和理解题意,确保你的理解和面试官的本意一致。题中的单链表,可不可以原地修改?是从高位到低位,还是低位到高位?如果是从低位到高位,那么问题很简单,是不是?只要两个指针移动(因为是等长的),对应位置相加,同时记录是否有进位,产生的结果存入新的链表中。


如果是从高到低,问题就复杂了,进位是万恶之源。这时,也许我们会想到reverse两个单链表(其实,这也是一道很好的面试题,如何做?考虑递归和递推两种算法),但这样做,是不是最好最坏情形都得遍历两次?好像不合题意。


如果新的链表的节点可以存一个或两个数字,那么,第一遍,将相应节点的数字相加,存入新的链表,并用一个flag标志整个操作中是否有进位。如果没有,结了;否则,再扫描一遍新的链表,将有两个数字的进位存到上一个节点。如果新的链表是双的,问题比较简单;如果新的链表还是单的,这一步也会很复杂,比如,10-〉9-〉9-〉12,如何转成1-〉1-〉0-〉0-〉2,本身也是一个很好的面试题。这时可能需要reverse链表再操作。


如果新的链表的节点只能存一个数字,那么能有什么办法?


也许你有更好的解决办法?期待。



当前位置: 传送门 ›› 待字闺中