I want to match those five numbers 3, 7, 8, 9, 87 through regular express.
1Here is my thought: 2 3- match those four numbers `3 7 8 9` var `^[3|7|8|9]$` 4- match number `87` var `^87$` 5 6Then combine them together, `(^[3|7|8|9]$|^87$)`. With some test, it seems correct. Is there any way to do that more efficiently? 7 8------------------------------- 9 10Q: 已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素，是的组成的三元组距离最小。 11三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为: 12Distance = max(|a[i] – b[j]|, |a[i] – c[k]|, |b[j] – c[k]|) 13请设计一个求最小三元组距离的最优算法，并分析时间复杂度。 14 15用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针， 16再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n) 17--------------------------------------------------------------------------------------------------------------------- 18Q:设计一个最优算法来查找一n个元素数组中的最大值和最小值。 19已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。 20 21把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较， 22把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是 N/2 次；在前面分组的基础上，那么可以得到结论， 23最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最大值和最小值的查找分别需要比较N/2 次和N/2 次； 24这样就可以找到最大值和最小值了，比较的次数为 25 N/2 * 3 = (3N)/2 次 26--------------------------------------------------------------------------------------------------------------------- 27Q:有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。 28从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够长的时间之后，能剩下多少条鱼？ 29 30用一个栈 31从左向右处理数据 321)遇到向右的鱼，压栈； 332)遇到向左的鱼，若栈空，结果+1；否则，将该鱼和栈顶比较，若栈顶鱼较大，则该鱼被吃掉，栈不变，处理下一个数据； 34 若栈顶鱼小，则弹出栈顶，继续与下一个比较，直到遇到较大的鱼，该鱼被吃掉；或者栈里鱼都比该鱼小，栈清空，结果+1 353)加上最终栈中鱼的数目 36-------------------------------------------------------------------------------------------------------------------- 37Q: Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of 38integers in two different ways: a^3+b^3=c^3+d^3. For example, 1729=9^3+10^3=1^3+12^3. 39Design an algorithm to find all taxicab numbers with a, b, c, and d less than N. 40 Version 1: Use time proportional to N2logN and space proportional to N2. 41 Version 2: Use time proportional to N2logN and space proportional to N. 42 43Hints: 44 Version 1: Form the sums a^3+b^3 and sort. 45 Version 2: Use a min-oriented priority queue with N items. 46-------------------------------------------------------------------------------------------------------------------- 47Q: 那地铁图 公交图查找，在实际的工程里用什么？ 48 49 R树划分区域, 线段树确定方案 50 51Q: 德导航那个林志玲的声音，他不是让林志玲一条条的录的，合成过程中用了二分图的一个演化算法 52 53-------------------------------------------------------------------------------------------------------------------- 54Q:有一个链表，每一个节点除了next指针指向一下节点以外， 55又多出了一个指针random，指向链表中的任何一个节点，包括null。请给出方法完成链表的深拷贝。 56 57这个问题的关键就在于random指针如何完成拷贝，next指针一次遍历就完成了，random指针拷贝的关键在于， 58如何找到random指向的节点对应的新的节点。一般来讲，大家会想到用map来保存旧的节点到新的节点的映射， 59这样得到的方法的时间复杂度为O(n)，空间复杂度为O(n)。 60下面是一个可行的方法：oldlist为原始链表，copylist为新的链表，oldnode为oldlist中的节点，copynode为copylist中的节点： 61 1. 根据oldlist，创建copylist，只拷贝next指针 62 2. 保存oldnode到oldnode.next的映射 63 3. 将oldlist中的oldnode的next指针指向copylist中对应的copynode 64 4. 将copylist中的copynode的random指针指向oldlist中对应的oldnode 65 5. 对于copylist中的每一个节点：copynode.random=copynode.random.random.next 66 6. 根据第2步，建立的映射，恢复oldlist 67 68上面这个方法，需要额外的映射。下面介绍一个巧妙的方法，可以省去映射的部分 69 1. 对oldlist中的节点，依次作如下的操作：对于第i个节点oldnode[i]，生成拷贝节点copynode[i]， 70 并且插入在oldnode[i]和oldnode[i+1]之间，最后一个节点直接附加到oldlist后面即可。 71 2. 处理每一个copynode的random拷贝，及对每一个copynode=oldnode.next, oldnode.next.random=oldnode.random.next 72 后面的next确保是copynode。 73 3. 通过如下的操作，恢复oldlist，以及生成copylist 1) oldnode.next = oldnode.next.next 2) 74 copynode.next = copynode.next.next 这里要注意，oldnode的最后一个节点，next是null 75--------------------------------------------------------------------------------------------------------------- 76Q:一个数组A，数字出现的情况，只有以下三种： 77 1. 一些数字只出现一次 78 2. 一些数字出现两次 79 3. 只有一个数字出现三次 80 81请给出方法，找到出现三次的数字。 82分析这个题目和“找数字”的题目比较相似，但是解法上类似么？之前的解法是检查某一位上的1的和，是否能够被3整除， 83因为整数是32位的，可以开辟一个 32位大小的数组，这也是常数空间的。那么这个题目可以用这个方法来解决么？ 84因为有不确定个数的数字出现了一次，这样可以产生的余数的种类也就比较多了。 那该怎么处理呢？ 85hashmap的方法被称为万金油，在牺牲了空间的条件下，很好的达到了O(n)的时间复杂度。 86如果要求常数空间的解法呢？之前的文章也有讨论，快排的时间复杂度是O(nlogn)，然后遍历一遍，找到连续三个相同的数字。 87后面这一遍遍历，可以省去，因为出现三次的数字只有一个。但总的时间复杂度仍是O(nlogn)。 88 89是否还有其他的方法呢？有的同学给出了如下的方法：可以取得A中所有数字的乘积p，我们假设p没有溢出。 90这是遍历数组中的每一个元素A[i]，查看 是否p % (A[i] * A[i] * A[i]) == 0，但此时，A[i]并不是最终要找到的数字， 91还需要遍历数组A，查看A[i]是否出现了三次。但这个方法整体的时间复杂度为O(n^2)。 92------------------------------------------------------------------------------------------------------------------- 93Q: 有数组A={5,3,8,9,16}，第一次遍历有：A = {3-5,8-3,9-8,16-9}={-2,5,1,7}，数组中元素和为-2+5+1+7=11；\ 94第二次遍历有：A = {5-(-2),1-5,7-1}={7，-4,6}，元素和为9.给定数组A，求第n次遍历之后，数组中元素的和。 95 96处理这样的题目，如果没有直接知道相关的原理，可以自己走一下一些具体的例子，这样就可以发现一些规律，根据这些规律， 97再去联想解决的完整方法。经过观察，我们可以发现： 98 * 对于第k次遍历而言，x_k_1、x_k_2、...、x_k_m，sum = x_k_m - x_k_1 99也就是说，第k次遍历结果的和，只与第一个和最后一个元素先关。下面，就来讨论，如何求得第一个和最后一个元素。 100我们看题目中的例子，先考虑第一个元素的变化 101 * 第一次遍历 k = 1时：-2=3-5 102 * 第二次遍历 k = 2时：7=5-(-2)=(8-3)-(3-5)=8-2*3+5 103 * 第三次遍历 k = 3时：-11=-4-7=(1-5)-(5-(-2)) = ((9-8)-(8-3)) - ((8-3)-(3-5))=9-3*8+3*3-5 104分析到此，想必大家已经能够明白这其中的规律，其实就是杨辉三角，老外叫帕斯卡三角。最后一个节点是类似的。 105而且，真个方法的时间复杂度与遍历的次数n有关，与数组的大小无关。 106------------------------------------------------------------------------------------------------------------------- 107Q:搜索引擎的查询提示(suggestion)是非常重要的一个功能。现在给定查询列表，以及每一个查询对应的频率。 108请设计一种查询提示的实现方案，要兼顾效果和速度。如果有其他更好的优化点，请给出详细说明。 109 110这个功能，在搜索引擎里是非常常用的。用户在逐个输入每一个查询词的时候，给出查询的提示，用户可以选择，完成查询的输入。 111这个过程，查询的提示必须要快。要不然，用户都输入完了，还没有提示，体验太差。那这个问题要怎么做呢？ 112给定的查询日志是这样的： 113query1 num1 114query2 num2 115query3 num3 116… 117queryn numn 118 119具体的query可能是“薛蛮子”“郭敬明”等等。用户输入时，会有哪些状态呢？ 120 * 薛 121 * 薛蛮 122 * 薛蛮子 123当用户输入完“薛”的时候，就要提示以“薛”开头的哪些查询，而且是查询频率最高的10个，一般是10个。 124这里是考虑总的查询的频率最高的10个，在实际的过程中，可以考虑当前热门的查询，可能总的次数比较少， 125但是近几天用户差得非常多，这样的查询也一定要能够提示。 126形式与目的我们都清楚了。具体做法也是比较多的，最直接的，容易想到trie树，因为上面列出的几种状态，就是前缀。 127那一棵前缀树，显然是最合适的。我们在这里，就不详细说明trie的结构，只给出如何应用trie树。trie树的构建： 128 * 对于所有查询，构建trie树，并且，对于查询结束的节点，进行标记，保存查询的频率。 129 * 由叶子节点开始向上，比如，叶子节点A，父节点为B，B存储top10的查询，包括：所有叶子节点代表的查询，以及， 130 如果B是查询结束节点，也包括B节点，按照频率排序的10个查询。 131 依次向上处理，父节点的top10，是所有子节点的top10合并而成。 132这样查询的时候，直接是对trie进行查询，到某一个节点，读取这个节点存储的top10查询即可，同时，这棵树，对于更新非常友好， 133可以新增频率，从叶子节点，回溯到根节点，即可。 134或者，采用trie树，不再节点存储top10查询，查询读取到可能类表之后再进行查询，这样会慢一些，但是内存开销稍微小一些。 135但，总的来说，trie树的内存开销是非常大的。那么，我们看下面的方法。 136一般，参与过搜索引擎的开发过程的，尤其是检索部分的同学，这个题目，第一个想法，可能不是trie树，而是倒排结构。 137总的来讲，应用倒排结构，有如下特点，也是和trie树进行对比： 138 * 查询快 139 * 方便压缩，节省内存 140 * 更新不方便，可以采用定期重建 141具体倒排的做法： 142 * 对于每一个查询的所有前缀，做为倒排的索引项，创建倒排 143 * 每一个倒排，只存储top10频率的查询 144除了上面介绍的之外，还需要考虑拼音等，思路大体相同。只不过更加需要注意内存的消耗。 145--------------------------------------------------------------------------------------------------------- 146Q: 从1到n，n个数字，每个数字只出现一次。现在，随机拿走一个数字，请给出方法，找到这个数字。 147如果随机拿走两个数字呢？如果随机拿走k个数字呢？ 148 149这个题目的含义是：n-1互不相同的整数，取值范围是[1,n]，请找到1-n中，没有出现的整数(好像更难理解了:))。 150当缺少一个数字的时候，很简单，计算1到n的和sum_more，然后再将n-1个整数求和，得到sum_less， 151则消失的数字就是(sum_more - sum_less)。 152如果消失两个数字呢？按照上面的方法，假设消失的两个数字分别为a和b，1 <= a, b <= n， 153我们可以得到a + b = sum_more - sum_less。只有一个等式，无法确定a和b的值是多少。根据我们以前学习解方程式的经验， 154我们还需要一个等式，才能确定a和b的值。现在已知的条件，就只有sum_more,sum_less，这两个分别是n个数的和，以及n-2个数的和， 155则最终还是要在这些数字的运算形式上做文章。考虑如下两个形式： 156 * square_sum_more = n个数的平方和 157 * square_sum_less = n-2个数的平方和 158有，square_sum_more - square_sum_less = a ^ 2 + b ^ 2。又构造了一个式子。这样解如下两个式子，得到a和b，即可： 159 * square_sum_more - square_sum_less = a ^ 2 + b ^ 2 160 * sum_more - sum_less = a + b 161解比较简单了，由第二个式子得：b = sum_more - sum_less - a，带入第一个式子，则第一个式子，只有a。 162如果消失三个数字呢？根据上面处理两个数字的情况，有如下的式子： 163 * sum_more - sum_less = a + b + c 164 * square_sum_more - square_sum_less = a ^ 2 + b ^ 2 + c ^ 2 165 * cube_sum_more - cube_sum_less = a ^ 3 + b ^ 3 + c ^ 3 166解出a，b，c即可。 167依次类推，当消失k个数字的时候，算法的时间复杂度为O(kn)。 168另外，微博上的一位同学@曹鹏博士，给出了一个O(nlogn)的解法，也是非常巧妙的，具体是采用分治法： 169知道1-n最低bit有多少个为0，多少个为1。然后统计一下，给出的数最低bit有多少个为0，多少个为1； 170然后就知道从最低bit为0的那部分取走了k0个数，从最低bit为1那部分取走了k1个数。 其中，k0 + k1 = k。 171然后把那些数按照最低bit为0，为1分开。问题变为两个子问题k0,k1，然后再考虑次低bit。很不错的解法。 172----------------------------------------------------------------------------------------------------------------- 173Q:给定一个数X，他的兄弟数Y定义为：是由X中的数字组合而成，并且Y是大于X的数中最小的。 174例如，38276的兄弟数字为38627。给定X，求Y。 175 176这个题目当然有暴力的方法，列出所有的排列组合，然后然后找到大于X中，最小的Y。即，找到兄弟数字。那有没有更好的方法呢？ 177不想对所有情况进行穷举，就要想办法，尽可能缩小要处理的范围，一般的思路，从右边开始，两两交换，查看是否可以找到Y， 178最开始考虑两位，进而考虑三位，依次类推，那么如何确定，要考虑多少位呢？ 179假设X的形式如下：x1x2x3...xky1y2y3y4，并且其中y1>y2>y3>y4，xk<y1。则，交换不可能在y1y2y3y4内部发生， 180以为这几个数字，任意两个交换，X值就变小了，而Y是大于X的。所以y1到y4是不行的。 181那么xk行么？完全可以，至少和y1交换，数字变大了。 那么到底要和哪个数字交换，进而保证变化最小呢？ 182很显然，要找到y1到y4中，大于xk的值里，最小的一个。这个值交换之后，既保证了不会增加太多，也不会减少。 183假设就是y3，此时Y是x1x2x3...y3y1y2xky4,这个数是从y3那位开始，大于X的，无论后面的几位是什么。 184显然易见，最小的Y就是y1y2xky4要从小到大排序的。 185 186下面以一个具体例子来说明上述过程： 18734722641 188首先找到，从右边开始的递增的、尽可能长的数位，这里是641。 18934722(641) 190则，选取前一位数字2，进行交换。641中，大于2的最小的值是4，则作如下交换： 19134724(621) 192为了得到最小值，对621，从小到大进行排序，得到 19334724126 194则，Y为34724126. 195------------------------------------------------------------------------------------------------------------- 196Q:有n对喜鹊。每一对可以表示为(x,y)，x、y是喜鹊的编号，并且任意一对，x总是小于y。(c,d)可以连接在(a,b)之后，当且仅当b<c。 197多对喜鹊连接在一起，就构建成了鹊桥。给定n对喜鹊，请你构建最长的鹊桥，来帮助有情人相会。 198 199首先，要理解这个题目的意思。具体例子说明，给定下面的例子： 200(15,40)(5,8)(1,10)(30,31)(34,35)(9,20)(36,37)(2,4)其中，(2,4)和(5,8)能够连接起来，(5,8)和(9,20)能够连接起来， 201则它们可以都连接起来，为(2,4)(5,8)(9,20)。这一段鹊桥，长度为3。依次类推，还有其他的情况。 202然后，理解了题意，该如何解决呢？假设(a,b)(c,d)(e,f)是可以连接起来的三对喜鹊。 203则它们的关系如下： b<c,d<e，有根据a<b,c<d,e<f。得到，a<b<c<d<e<f，即b<d<f(从a<c<e出发考虑，也是一样的)。 204我们可以想象，以每一对喜鹊的第二只编号为基准，进行排序，最终的结果，可以通过如下列表产生。 205(2,4)(5,8)(1,10)(9,20)(30,31)(34,35)(36,37)(15,40)怎么找到最长的鹊桥呢？其实就是在上表中，找到最长递增子序列， 206只不过，在比较连个喜鹊对(a,b)(c,d)的时候，是b和c进行比较即可。这个时间复杂度是O(n^2)的。 207----------------------------------------------------------------------------------------------------------------- 208Q:n根长度不一的棍子，判断是否有三根棍子可以构成三角形，并且找到周长最长的三角形。 209 210首先能够构成三角形的三根棍子需要满足什么条件呢？这个简直就是常识了： 211最长棍子的长度 < 另外两根棍子的长度和 212这是重要条件。 213那么接下来该怎么办呢？暴力法——不要总觉得这是耻辱，要这样想：这是一个好开端。三条边，三层循环。时间复杂度为O(n^3)。 214这在一般的题目中，都是无法接受的。如何改进的呢？棍子有长有短，我们要找到的是周长最长的。 215我们可以对棍子的长度，从大到小排序。从最长的开始找符合构成三角形条件的。找到的第一个就是周长最长的。 216下面我们来说明，为什么第一个找到的，就是最长的。假设我们有如下长度的棍子，并且长度一次递减。 217abcdefg假设opq是第一个可以构成三角形的棍子，假设还存在xyz，构成三角形，且，x+y+z > o + p + q, 218因为opq是第一个三角形，则x<=o。则y+z > p+q，任取y、z，则可以找到，o，y，z为一个三角形，周长大于opq， 219并且，这个三角形，在opq之前找到(因为y或者z，大于p或者q，先遍历到)。这个与adf是第一个的假设是矛盾的。 220所以，不存在xyz构成三角形，周长大于adf。 221那么如果找到第一个能够构成三角形的三根棍子呢？现在棍子的长度已经是排序的。 222abcdefg很明显，我们只需要依次考虑，相邻三个元素是否能够构成三角形即可。因为，如果acd构成三角形，abc一定是， 223而且，周长还要更长。所以这里O(n)，就可以找到周长最长的三角形。前面排序是O(nlogn)。则，总的时间复杂度是O(nlogn). 224-------------------------------------------------------------------------------------------------------------------- 225Q: 一个整数，可以表示为二进制的形式，请给出尽可能多的方法对二进制进行逆序操作。 226例如：10000110 11011000的逆序为 00011011 01100001 227 228A: 229直接的方法，很容易想到：有如下代码： int v = 111; 230int r = v; 231int s = 32; 232for (; 0 != v; v >>= 1) { 233 r <<= 1; 234 r |= v & 1; 235 s--; 236} 237r <<= s; 238System.out.println(r); 239代码比较好理解，取到v的最低位，作为r的最高位；v每取一次最低位，则右移一位；r每确定一位，则左移一位。 240同时记录移动了多少位，最终要补齐。 241 242通过查表的方法在遇到位操作的问题时，往往题目中限定了总的位数，比如这个题目，我们可以认为32位。 243这就给我们带来了一个以空间换时间的解决思路：查表法。 244位数是固定的，可以申请空间，存储预先计算好的结果，在计算其他的结果的时候，则查表即可。 24532位相对于查表来讲，还是太大了。既然这样缩小范围，32个bit，也就是4个byte。每个byte 8bit，可以表示0-255的整数。 246可以通过申请256大小的数组，保存这256个整数，二进制逆序之后的整数。然后将一个32位的整数，划分为4个byte， 247每一个byte查表得到逆序的整数：r1,r2,r3,r4。按照r4r3r2r1顺序拼接二进制得到的结果就是最终的答案。 248 249我们这里主要分析这个巧妙的方法，核心思想是：分治法。即： 250 * 逆序32位分解为两个逆序16位的 251 * 逆序16位分解为两个逆序8位的 252 * 逆序8位分解为两个逆序4位的 253 * 逆序4位分解为两个逆序2位的 254 255最后一个2位的逆序，直接交换即可。也就是分治递归的终止条件。但是，在上面的过程中，还没有应用到位操作的技巧 256。根据动态规划的思想，我们可以自底向上的解决这个问题： 257 * 每2位为一组，进行交换，完成2位逆序 258 * 每4位为一组，前面2位与后面2位交换，完成4位逆序 259 * 每8位为一组，前面4位和后面4为交换，完成8位的逆序 260 * 每16位为一组，前面8位和后面8位交换，完成16位的逆序 261 * 2组16位的交换，完成32位的逆序 262 263示例代码如下： 264int v = 111; 265v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 266v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 267v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 268v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 269v = ( v >> 16 ) | ( v << 16); 270------------------------------------------------------------------------------------------------------------------ 271Q:输入数组[a1,a2,...,an,b1,b2,...,bn]，构造函数，使得输出为，[a1,b1,a2,b2,...,an,bn]，注意：方法要是in-place的。 272 273A:通过观察输入输出的格式，直接通过将b1进行交换，直至目标的位置，其他元素也如此操作。直到完成变换。如下的过程： 274a1 a2 a3 a4 b1 b2 b3 b4 275确定b1的位置，b1要和前面3个元素依次交换。 276a1b1a2a3a4b2b3b4 277确定b2的位置，b2要和前面的2个元素一次交换，同样为了保证in-place。注意交换次数少了一次。 278a1b1a2b2a3a4b3b4 279依次确定b3和b4的位置，b4是最后的元素，不需进行交换，b3需要交换一次。 280a1b1a2b2a3b3a4b4 281通过上面的分析，则整体的交换次数，3+2+1=6，不失一般性(n-1)+…+1，时间复杂度O(n^2)。 282 283特别的方法同样针对上面的例子： 284第一步：交换最中间的一对元素，得到 285a1a2a3b1a4b2b3b4 286第二步：交换最中间的两对元素，得到 287a1a2b1a3b2a4b3b4 288第三步：交换最中间的三对元素，得到 289a1b1a2b2a3b3a4b4 290完毕，得到结果。 291在上面的交换中，交换的次数分别为1,2,3，推而广之，1,…,n-1，则时间复杂度仍旧是O(n^2)的。 292 293in-place的O(n)方法这个问题，是存在O(n)时间复杂度的in-place算法的。但是，并不是很好理解。 294首先，对2n=3^k - 1的情况下，k是整数。这时候可以通过几个cyclic shift解决。 295每个cycle的起始位置是3^i, i=0,1,...,k-1. cycle里面元素下标的符合这样的模式(3^i×2^j) mod (2n+1) 296举例说明：k=2时，2n=8. 297假设一个数列是[1，2，3，4，5，6，7，8] 298那么这几个cycle是 299i=0, 3^i=1, [1,2,4,8,16,32] mod 9 = [1,2,4,8,7,5] 300i=1， 3^i=3, [3,6] mod 9 = [3,6] 301显然这些cycle都是闭合的，比如对[1,2,4,8,7,5]， 5×2 mod 9 = 1， 对[3,6] 6×2 mod 9 = 3 302 303下面做这两个cyclic shift 304做完第一个后： 305[1，2，3，4，5，6，7，8] -> [5，1，3，2，7，6，8，4] 306做完第二个后： 307[5，1，3，2，7，6，8，4] -> [5，1，6，2，7，3，8，4] 308搞定。 309 310其次对2n！=3^k - 1的情况下，找一个最大的m，m满足2m=3^k - 1并且m 比如假设n=6，那么m=4. 311假设一个素列A=[1，2，3，4，5，6，7，8，9，10，11，12] 312首先A[m+1,...,n+m]做一个距离为m的右循环。 313也就是[5,6,7,8,9,10]做一个距离为m的右循环，变成[7,8,9,10,5,6] 314做完这个循环，[1，2，3，4，5，6，7，8，9，10，11，12]->[1，2，3，4，7，8，9，10，5, 6, 11，12] 315然后对前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] 316然后对于下的2*(n-m)项[5，6，11，12]递归操作。 317 318def getIndex(curIdx, N): 319 return (curIdx%2)*N + (curIdx/2) 320 321def convertArray(arr): 322 N = len(arr)/2 323 for curIdx in range(len(arr)): 324 swapIdx = getIndex(curIdx, N) 325 while swapIdx < curIdx: 326 swapIdx = getIndex(swapIdx, N) 327 arr[curIdx], arr[swapIdx] = arr[swapIdx], arr[curIdx] 328 329 330def convertArray_extraspace(arr): 331 N = len(arr)/2 332 return [arr[getIndex(i, N)] for i in range(len(arr))] 333 334def main(): 335 336if __main__ == 'main' 337 main() Q: n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。蚂蚁爬到终点会掉下来。两只蚂蚁相遇时，只能调头爬回去。 对于每一只蚂蚁i，给定其距离竿子左端的距离x[i]，但是我们不知道蚂蚁的初始朝向。计算，所有蚂蚁掉落需要的最短时间和最长时间。