阿里面试算法题（转载）

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

I want to match those five numbers 3, 7, 8, 9, 87 through regular express. Here is my thought:

match those four numbers 3 7 8 9 var ^[3|7|8|9]\(
match number 87 var ^87\)

Then combine them together, (^[3|7|8|9]\(|^87\)). With some test, it seems correct. Is there any way to do that more efficiently?

用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)
#

Q：设计一个最优算法来查找一个n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。

把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是 N/2 次；在前面分组的基础上，那么可以得到结论，最小值一定在每一组的左边部分找，最大值一定在每一组的右边部分找，最大值和最小值的查找分别需要比较N/2 次和N/2 次；这样就可以找到最大值和最小值了，比较的次数为　　　　　　N/2 * 3 = (3N)/2 次
#

Q：有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够长的时间之后，能剩下多少条鱼？

用一个栈从左向右处理数据 1)遇到向右的鱼，压栈； 2)遇到向左的鱼，若栈空，结果+1；否则，将该鱼和栈顶比较，若栈顶鱼较大，则该鱼被吃掉，栈不变，处理下一个数据；若栈顶鱼小，则弹出栈顶，继续与下一个比较，直到遇到较大的鱼，该鱼被吃掉；或者栈里鱼都比该鱼小，栈清空，结果+1 3)加上最终栈中鱼的数目
#

Q: Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: a^3+b^3=c^3+d^3. For example, 1729=9^3+10^3=1^3+12^3. Design an algorithm to find all taxicab numbers with a, b, c, and d less than N. Version 1: Use time proportional to N2logN and space proportional to N2. Version 2: Use time proportional to N2logN and space proportional to N.

Hints: Version 1: Form the sums a^3+b^3 and sort. Version 2: Use a min-oriented priority queue with N items.
#

Q: 那地铁图公交图查找，在实际的工程里用什么？

R树划分区域，线段树确定方案

Q: 高德导航那个林志玲的声音，他不是让林志玲一条条的录的，合成过程中用了二分图的一个演化算法

Q：有一个链表，每一个节点除了next指针指向一下节点以外，又多出了一个指针random，指向链表中的任何一个节点，包括null。请给出方法完成链表的深拷贝。

这个问题的关键就在于random指针如何完成拷贝，next指针一次遍历就完成了，random指针拷贝的关键在于，如何找到random指向的节点对应的新的节点。一般来讲，大家会想到用map来保存旧的节点到新的节点的映射，这样得到的方法的时间复杂度为O(n)，空间复杂度为O(n)。下面是一个可行的方法：oldlist为原始链表，copylist为新的链表，oldnode为oldlist中的节点，copynode为copylist中的节点： 1. 根据oldlist，创建copylist，只拷贝next指针 2. 保存oldnode到oldnode.next的映射 3. 将oldlist中的oldnode的next指针指向copylist中对应的copynode 4. 将copylist中的copynode的random指针指向oldlist中对应的oldnode 5. 对于copylist中的每一个节点：copynode.random=copynode.random.random.next 6. 根据第2步，建立的映射，恢复oldlist

上面这个方法，需要额外的映射。下面介绍一个巧妙的方法，可以省去映射的部分 1. 对oldlist中的节点，依次作如下的操作：对于第i个节点oldnode[i]，生成拷贝节点copynode[i]，并且插入在oldnode[i]和oldnode[i+1]之间，最后一个节点直接附加到oldlist后面即可。 2. 处理每一个copynode的random拷贝，及对每一个copynode=oldnode.next, oldnode.next.random=oldnode.random.next 后面的next确保是copynode。 3. 通过如下的操作，恢复oldlist，以及生成copylist 1) oldnode.next = oldnode.next.next 2) copynode.next = copynode.next.next 这里要注意，oldnode的最后一个节点，next是null
#

Q：一个数组A，数字出现的情况，只有以下三种： 1. 一些数字只出现一次 2. 一些数字出现两次 3. 只有一个数字出现三次

请给出方法，找到出现三次的数字。分析这个题目和“找数字”的题目比较相似，但是解法上类似么？之前的解法是检查某一位上的1的和，是否能够被3整除，因为整数是32位的，可以开辟一个 32位大小的数组，这也是常数空间的。那么这个题目可以用这个方法来解决么？因为有不确定个数的数字出现了一次，这样可以产生的余数的种类也就比较多了。那该怎么处理呢？ hashmap的方法被称为万金油，在牺牲了空间的条件下，很好的达到了O(n)的时间复杂度。如果要求常数空间的解法呢？之前的文章也有讨论，快排的时间复杂度是O(nlogn)，然后遍历一遍，找到连续三个相同的数字。后面这一遍遍历，可以省去，因为出现三次的数字只有一个。但总的时间复杂度仍是O(nlogn)。

是否还有其他的方法呢？有的同学给出了如下的方法：可以取得A中所有数字的乘积p，我们假设p没有溢出。这是遍历数组中的每一个元素A[i]，查看是否p % (A[i] * A[i] * A[i]) == 0，但此时，A[i]并不是最终要找到的数字，还需要遍历数组A，查看A[i]是否出现了三次。但这个方法整体的时间复杂度为O(n^2)。
#

Q: 有数组A={5,3,8,9,16}，第一次遍历有：A = {3-5,8-3,9-8,16-9}={-2,5,1,7}，数组中元素和为-2+5+1+7=11；
第二次遍历有：A = {5-(-2),1-5,7-1}={7，-4,6}，元素和为9.给定数组A，求第n次遍历之后，数组中元素的和。

处理这样的题目，如果没有直接知道相关的原理，可以自己走一下一些具体的例子，这样就可以发现一些规律，根据这些规律，再去联想解决的完整方法。经过观察，我们可以发现： * 对于第k次遍历而言，x_k_1、x_k_2、…、x_k_m，sum = x_k_m - x_k_1 也就是说，第k次遍历结果的和，只与第一个和最后一个元素相关。下面，就来讨论，如何求得第一个和最后一个元素。我们看题目中的例子，先考虑第一个元素的变化 * 第一次遍历 k = 1时：-2=3-5 * 第二次遍历 k = 2时：7=5-(-2)=(8-3)-(3-5)=8-23+5 * 第三次遍历 k = 3时：-11=-4-7=(1-5)-(5-(-2)) = ((9-8)-(8-3)) - ((8-3)-(3-5))=9-38+3*3-5 分析到此，想必大家已经能够明白这其中的规律，其实就是杨辉三角，老外叫帕斯卡三角。最后一个节点是类似的。而且，整个方法的时间复杂度与遍历的次数n有关，与数组的大小无关。
#

Q：搜索引擎的查询提示(suggestion)是非常重要的一个功能。现在给定查询列表，以及每一个查询对应的频率。请设计一种查询提示的实现方案，要兼顾效果和速度。如果有其他更好的优化点，请给出详细说明。

这个功能，在搜索引擎里是非常常用的。用户在逐个输入每一个查询词的时候，给出查询的提示，用户可以选择，完成查询的输入。这个过程，查询的提示必须要快。要不然，用户都输入完了，还没有提示，体验太差。那这个问题要怎么做呢？给定的查询日志是这样的： query1 num1 query2 num2 query3 num3 … queryn numn

具体的query可能是“薛蛮子”“郭敬明”等等。用户输入时，会有哪些状态呢？ * 薛 * 薛蛮 * 薛蛮子当用户输入完“薛”的时候，就要提示以“薛”开头的哪些查询，而且是查询频率最高的10个，一般是10个。这里是考虑总的查询的频率最高的10个，在实际的过程中，可以考虑当前热门的查询，可能总的次数比较少，但是近几天用户查得非常多，这样的查询也一定要能够提示。形式与目的我们都清楚了。具体做法也是比较多的，最直接的，容易想到trie树，因为上面列出的几种状态，就是前缀。那一棵前缀树，显然是最合适的。我们在这里，就不详细说明trie的结构，只给出如何应用trie树。trie树的构建： * 对于所有查询，构建trie树，并且，对于查询结束的节点，进行标记，保存查询的频率。 * 由叶子节点开始向上，比如，叶子节点A，父节点为B，B存储top10的查询，包括：所有叶子节点代表的查询，以及，如果B是查询结束节点，也包括B节点，按照频率排序的10个查询。依次向上处理，父节点的top10，是所有子节点的top10合并而成。这样查询的时候，直接是对trie进行查询，到某一个节点，读取这个节点存储的top10查询即可，同时，这棵树，对于更新非常友好，可以新增频率，从叶子节点，回溯到根节点，即可。或者，采用trie树，不再节点存储top10查询，查询读取到可能列表之后再进行查询，这样会慢一些，但是内存开销稍微小一些。但，总的来说，trie树的内存开销是非常大的。那么，我们看下面的方法。一般，参与过搜索引擎的开发过程的，尤其是检索部分的同学，这个题目，第一个想法，可能不是trie树，而是倒排结构。总的来讲，应用倒排结构，有如下特点，也是和trie树进行对比： * 查询快 * 方便压缩，节省内存 * 更新不方便，可以采用定期重建具体倒排的做法： * 对于每一个查询的所有前缀，做为倒排的索引项，创建倒排 * 每一个倒排，只存储top10频率的查询除了上面介绍的之外，还需要考虑拼音等，思路大体相同。只不过更加需要注意内存的消耗。
#

Q: 从1到n，n个数字，每个数字只出现一次。现在，随机拿走一个数字，请给出方法，找到这个数字。如果随机拿走两个数字呢？如果随机拿走k个数字呢？

这个题目的含义是：n-1互不相同的整数，取值范围是[1,n]，请找到1-n中，没有出现的整数(好像更难理解了：))。当缺少一个数字的时候，很简单，计算1到n的和sum_more，然后再将n-1个整数求和，得到sum_less，则消失的数字就是(sum_more - sum_less)。如果消失两个数字呢？按照上面的方法，假设消失的两个数字分别为a和b，1 <= a, b <= n，我们可以得到a + b = sum_more - sum_less。只有一个等式，无法确定a和b的值是多少。根据我们以前学习解方程式的经验，我们还需要一个等式，才能确定a和b的值。现在已知的条件，就只有sum_more,sum_less，这两个分别是n个数的和，以及n-2个数的和，则最终还是要在这些数字的运算形式上做文章。考虑如下两个形式： * square_sum_more = n个数的平方和 * square_sum_less = n-2个数的平方和有，square_sum_more - square_sum_less = a ^ 2 + b ^ 2。又构造了一个式子。这样解如下两个式子，得到a和b，即可： * square_sum_more - square_sum_less = a ^ 2 + b ^ 2 * sum_more - sum_less = a + b 解比较简单了，由第二个式子得：b = sum_more - sum_less - a，带入第一个式子，则第一个式子，只有a。如果消失三个数字呢？根据上面处理两个数字的情况，有如下的式子： * sum_more - sum_less = a + b + c * square_sum_more - square_sum_less = a ^ 2 + b ^ 2 + c ^ 2 * cube_sum_more - cube_sum_less = a ^ 3 + b ^ 3 + c ^ 3 解出a，b，c即可。依次类推，当消失k个数字的时候，算法的时间复杂度为O(kn)。另外，微博上的一位同学@曹鹏博士，给出了一个O(nlogn)的解法，也是非常巧妙的，具体是采用分治法：知道1-n最低bit有多少个为0，多少个为1。然后统计一下，给出的数最低bit有多少个为0，多少个为1；然后就知道从最低bit为0的那部分取走了k0个数，从最低bit为1那部分取走了k1个数。其中，k0 + k1 = k。然后把那些数按照最低bit为0，为1分开。问题变为两个子问题k0,k1，然后再考虑次低bit。很不错的解法。
#

Q：给定一个数X，他的兄弟数Y定义为：是由X中的数字组合而成，并且Y是大于X的数中最小的。例如，38276的兄弟数字为38627。给定X，求Y。

这个题目当然有暴力的方法，列出所有的排列组合，然后找到大于X中，最小的Y。即，找到兄弟数字。那有没有更好的方法呢？不想对所有情况进行穷举，就要想办法，尽可能缩小要处理的范围，一般的思路，从右边开始，两两交换，查看是否可以找到Y，最开始考虑两位，进而考虑三位，依次类推，那么如何确定，要考虑多少位呢？假设X的形式如下：x1x2x3…xky1y2y3y4，并且其中y1>y2>y3>y4，xk<y1。则，交换不可能在y1y2y3y4内部发生，因为这几个数字，任意两个交换，X值就变小了，而Y是大于X的。所以y1到y4是不行的。那么xk行么？完全可以，至少和y1交换，数字变大了。那么到底要和哪个数字交换，进而保证变化最小呢？很显然，要找到y1到y4中，大于xk的值里，最小的一个。这个值交换之后，既保证了不会增加太多，也不会减少。假设就是y3，此时Y是x1x2x3…y3y1y2xky4，这个数是从y3那位开始，大于X的，无论后面的几位是什么。显而易见，最小的Y就是y1y2xky4要从小到大排序的。

下面以一个具体例子来说明上述过程： 34722641 首先找到，从右边开始的递增的、尽可能长的数位，这里是641。 34722(641) 则，选取前一位数字2，进行交换。641中，大于2的最小的值是4，则作如下交换： 34724(621) 为了得到最小值，对621，从小到大进行排序，得到 34724126 则，Y为34724126.
#

Q：有n对喜鹊。每一对可以表示为(x,y)，x、y是喜鹊的编号，并且任意一对，x总是小于y。(c,d)可以连接在(a,b)之后，当且仅当b<c。多对喜鹊连接在一起，就构建成了鹊桥。给定n对喜鹊，请你构建最长的鹊桥，来帮助有情人相会。

首先，要理解这个题目的意思。具体例子说明，给定下面的例子： (15,40)(5,8)(1,10)(30,31)(34,35)(9,20)(36,37)(2,4)其中，(2,4)和(5,8)能够连接起来，(5,8)和(9,20)能够连接起来，则它们可以都连接起来，为(2,4)(5,8)(9,20)。这一段鹊桥，长度为3。依次类推，还有其他的情况。然后，理解了题意，该如何解决呢？假设(a,b)(c,d)(e,f)是可以连接起来的三对喜鹊。则它们的关系如下： b<c,d<e，有根据a<b,c<d,e<f。得到，a<b<c<d<e<f，即b<d<f(从a<c<e出发考虑，也是一样的)。我们可以想象，以每一对喜鹊的第二只编号为基准，进行排序，最终的结果，可以通过如下列表产生。 (2,4)(5,8)(1,10)(9,20)(30,31)(34,35)(36,37)(15,40)怎么找到最长的鹊桥呢？其实就是在上表中，找到最长递增子序列，只不过，在比较两个喜鹊对(a,b)(c,d)的时候，是b和c进行比较即可。这个时间复杂度是O(n^2)的。
#

Q:n根长度不一的棍子，判断是否有三根棍子可以构成三角形，并且找到周长最长的三角形。

首先能够构成三角形的三根棍子需要满足什么条件呢？这个简直就是常识了：最长棍子的长度 < 另外两根棍子的长度和这是重要条件。那么接下来该怎么办呢？暴力法——不要总觉得这是耻辱，要这样想：这是一个好开端。三条边，三层循环。时间复杂度为O(n^3)。这在一般的题目中，都是无法接受的。如何改进的呢？棍子有长有短，我们要找到的是周长最长的。我们可以对棍子的长度，从大到小排序。从最长的开始找符合构成三角形条件的。找到的第一个就是周长最长的。下面我们来说明，为什么第一个找到的，就是最长的。假设我们有如下长度的棍子，并且长度一次递减。 abcdefg 假设opq是第一个可以构成三角形的棍子，假设还存在xyz，构成三角形，且，x+y+z > o + p + q, 因为opq是第一个三角形，则x<=o。则y+z > p+q，任取y、z，则可以找到，o，y，z为一个三角形，周长大于opq，并且，这个三角形，在opq之前找到(因为y或者z，大于p或者q，先遍历到)。这个与opq是第一个的假设是矛盾的。所以，不存在xyz构成三角形，周长大于opq。

那么如果找到第一个能够构成三角形的三根棍子呢？现在棍子的长度已经是排序的。 abcdefg 很明显，我们只需要依次考虑，相邻三个元素是否能够构成三角形即可。因为，如果acd构成三角形，abc一定是，而且，周长还要更长。所以这里O(n)，就可以找到周长最长的三角形。前面排序是O(nlogn)。则，总的时间复杂度是O(nlogn).
#

Q: 一个整数，可以表示为二进制的形式，请给出尽可能多的方法对二进制进行逆序操作。例如：10000110 11011000的逆序为 00011011 01100001

A: 直接的方法，很容易想到：有如下代码：

 1int v = 111;
 2int r = v;
 3int s = 32;
 4for (; 0 != v; v >>= 1) {
 5    r <<= 1;
 6    r |= v & 1;
 7    s--;
 8}
 9r <<= s;
10System.out.println(r);

代码比较好理解，取到v的最低位，作为r的最高位；v每取一次最低位，则右移一位；r每确定一位，则左移一位。同时记录移动了多少位，最终要补齐。

通过查表的方法，在遇到位操作的问题时，往往题目中限定了总的位数，比如这个题目，我们可以认为32位。这就给我们带来了一个以空间换时间的解决思路：查表法。位数是固定的，可以申请空间，存储预先计算好的结果，在计算其他的结果的时候，则查表即可。 32位相对于查表来讲，还是太大了。既然这样缩小范围，32个bit，也就是4个byte。每个byte 8bit，可以表示0-255的整数。可以通过申请256大小的数组，保存这256个整数，二进制逆序之后的整数。然后将一个32位的整数，划分为4个byte，每一个byte查表得到逆序的整数：r1,r2,r3,r4。按照r4r3r2r1顺序拼接二进制得到的结果就是最终的答案。

我们这里主要分析这个巧妙的方法，核心思想是：分治法。即： * 逆序32位分解为两个逆序16位的 * 逆序16位分解为两个逆序8位的 * 逆序8位分解为两个逆序4位的 * 逆序4位分解为两个逆序2位的

最后一个2位的逆序，直接交换即可。也就是分治递归的终止条件。但是，在上面的过程中，还没有应用到位操作的技巧。根据动态规划的思想，我们可以自底向上的解决这个问题： * 每2位为一组，进行交换，完成2位逆序 * 每4位为一组，前面2位与后面2位交换，完成4位逆序 * 每8位为一组，前面4位和后面4位交换，完成8位的逆序 * 每16位为一组，前面8位和后面8位交换，完成16位的逆序 * 2组16位的交换，完成32位的逆序

示例代码如下：

1int v = 111;
2v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
3v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
4v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
5v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
6v = ( v >> 16 ) | ( v << 16);

Q：输入数组[a1,a2,…,an,b1,b2,…,bn]，构造函数，使得输出为，[a1,b1,a2,b2,…,an,bn]，注意：方法要是in-place的。

A：通过观察输入输出的格式，直接通过将b1进行交换，直至目标的位置，其他元素也如此操作。直到完成变换。如下的过程： a1 a2 a3 a4 b1 b2 b3 b4 确定b1的位置，b1要和前面3个元素依次交换。 a1b1a2a3a4b2b3b4 确定b2的位置，b2要和前面的2个元素依次交换，同样为了保证in-place。注意交换次数少了一次。 a1b1a2b2a3a4b3b4 依次确定b3和b4的位置，b4是最后的元素，不需进行交换，b3需要交换一次。 a1b1a2b2a3b3a4b4 通过上面的分析，则整体的交换次数，3+2+1=6，不失一般性(n-1)+…+1，时间复杂度O(n^2)。

特别的方法同样针对上面的例子：第一步：交换最中间的一对元素，得到 a1a2a3b1a4b2b3b4 第二步：交换最中间的两对元素，得到 a1a2b1a3b2a4b3b4 第三步：交换最中间的三对元素，得到 a1b1a2b2a3b3a4b4 完毕，得到结果。在上面的交换中，交换的次数分别为1,2,3，推而广之，1,…,n-1，则时间复杂度仍旧是O(n^2)的。

in-place的O(n)方法是存在的。但是，并不是很好理解。首先，对于2n=3^k - 1的情况，k是整数。这时候可以通过几个cyclic shift解决。每个cycle的起始位置是3^i, i=0,1,…,k-1. cycle里面元素下标的符合这样的模式(3^i×2^j) mod (2n+1) 举例说明：k=2时，2n=8. 假设一个数列是[1，2，3，4，5，6，7，8] 那么这几个cycle是 i=0, 3^i=1, [1,2,4,8,16,32] mod 9 = [1,2,4,8,7,5] i=1， 3^i=3, [3,6] mod 9 = [3,6] 显然这些cycle都是闭合的，比如对[1,2,4,8,7,5]， 5×2 mod 9 = 1，对[3,6] 6×2 mod 9 = 3

下面做这两个cyclic shift 做完第一个后： [1，2，3，4，5，6，7，8] -> [5，1，3，2，7，6，8，4] 做完第二个后： [5，1，3，2，7，6，8，4] -> [5，1，6，2，7，3，8，4] 搞定。

其次对2n！=3^k - 1的情况下，找一个最大的m，m满足2m=3^k - 1并且m 比如假设n=6，那么m=4. 假设一个素列A=[1，2，3，4，5，6，7，8，9，10，11，12] 首先对A[m+1,…,n+m]做一个距离为m的右循环。也就是[5,6,7,8,9,10]做一个距离为m的右循环，变成[7,8,9,10,5,6] 做完这个循环，[1，2，3，4，5，6，7，8，9，10，11，12]->[1，2，3，4，7，8，9，10，5, 6, 11，12] 然后对前2m项，做1的操作，[1，2，3，4，7，8，9，10，5, 6, 11，12]->[7，1，8，2，9，3，10，4，5, 6, 11，12] 然后对剩下的2*(n-m)项[5，6，11，12]递归操作。

 1def getIndex(curIdx, N):
 2	return (curIdx%2)*N + (curIdx/2)
 3
 4def convertArray(arr):
 5	N = len(arr)/2
 6	for curIdx in range(len(arr)):
 7		swapIdx = getIndex(curIdx, N)
 8		while swapIdx < curIdx:
 9			swapIdx = getIndex(swapIdx, N)
10		arr[curIdx], arr[swapIdx] = arr[swapIdx], arr[curIdx]
11
12
13def convertArray_extraspace(arr):
14	N = len(arr)/2
15	return [arr[getIndex(i, N)] for i in range(len(arr))]
16
17def main():
18	pass
19
20if __name__ == '__main__':
21	main()

Q: n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。蚂蚁爬到终点会掉下来。两只蚂蚁相遇时，只能调头爬回去。对于每一只蚂蚁i，给定其距离竿子左端的距离x[i]，但是我们不知道蚂蚁的初始朝向。计算，所有蚂蚁掉落需要的最短时间和最长时间。

我们在摘要中说道，这个题目其实是考察大家想象力的。想象力在哪里呢？我们首先来看看最短时间的情况，直觉上来讲，所有的蚂蚁都朝最近的一端走，是需要最短时间的。那么这时，会不会发生碰撞呢？显然是不能的，A和B是两只不同的蚂蚁。 …BA … 假设A到左端近，距离为LA<L/2。B到右端近，距离为LB<L/2。LA+LB<L。但从上表看，LA+LB显然要大于L。下面考虑最长时间的情况，也是该发挥想象力的地方。当两只蚂蚁相遇的时候，本来是要调头爬回去的。这与直接交错走过去有什么不同呢？蚂蚁的速度是一样的。大家可以举几个具体的例子，看看这两种情况，差别在哪里。例如： B A * 当相遇调头时，A和B都掉下来的最长时间是4秒。A向左一格，然后调头向右三格 * 当相遇交错走过时，A向左走三格掉落，B向右走四格掉落。则最长时间为4秒。

这并不是巧合。可以认为是同样的情况。主要的原因就是蚂蚁的速度是相同的，可以认为是独立的。这样，求所有蚂蚁都掉落的最长时间，就是找离某一端距离最长的蚂蚁，然后向着这一端走，所需要的时间。算法的时间复杂度为O(n)。后面求最长时间的关键就是，发挥想象，找到调头和交错走过实际上是一样的。就搞定了。

用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针， 再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)#

Hints: Version 1: Form the sums a^3+b^3 and sort. Version 2: Use a min-oriented priority queue with N items.#

Related

用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)
#

Hints: Version 1: Form the sums a^3+b^3 and sort. Version 2: Use a min-oriented priority queue with N items.
#