第三十四~三十五章：格子取数，

作者：July、caopengcs、绿色夹克衫。致谢：西芹_new，陈利人，

时间：二零一三年八月二十三日。

    再过一个半月，即到2013年10月11日，便是本博客开通3周年之际，巧的是，那天刚好也是我的25岁生日。写博近3年，访问量趋近500万，无法确切知道帮助了多少人影响了多少人，但有些文章和一些系列是我比较喜欢的，如这三篇：从B树、B+树、B*树谈到R 树；教你如何迅速秒杀掉：99%的海量数据处理面试题；支持向量机通俗导论（理解SVM的三层境界）。

    以及这2个系列：数据挖掘十大算法系列，程序员编程艺术。

    当然，还有很多文章或系列自己也比较喜欢（如微软面试100题系列，经典算法研究系列等等），只是上面的文章或系列更具代表性。

    但若论在上述文章或系列中，哪篇文章或系列对人找工作的帮助最大，则应该是：

第三十四章、格子取数问题

    题目详情：有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。

    题目分析：此题是去年2013年搜狗的校招笔试题。初看到此题，因为要让两次走下来的路径总和最大，读者可能最初想到的思路可能是让每一次的路径都是最优的，即不顾全局，只看局部，让第一次和第二次的路径都是最优。

    但问题马上就来了，虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图：

    上图中，图一是原始图，那么我们有以下两种走法可供我们选择：

    也就是说，上面图二中的走法太追求每一次最优，所以第一次最优，导致第二次将是很差；而图三第一次虽然不是最优，但保证了第二次不差，所以图三的结果优于图二。由此可知不要只顾局部而贪图一时最优，而丧失了全局最优。

    局部贪优不行，我们可以考虑穷举，但最终将导致复杂度过高，所以咱们得另寻良策。

    @西芹_new，针对此题，可以使用直接搜索法，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下：

    上述解法一的搜索解法是的时间复杂度是指数型的，如果是只走一次的话，是经典的dp。

    故正如@绿色夹克衫所说：此题也可以用动态规划求解，主要思路就是同时DP 2次所走的状态。

• 经过8步后，一定处于右下角(8)；
• 那么经过5步后(s = 5)，肯定会处于编号为5的位置；
• 3步后肯定处于编号为3的位置；
• s = 4的时候，处于编号为4的位置，此时对于方格中，共有5（相当于n）个不同的位置，也是所有编号中最多的。

  上面（式一）所示的这个递推看起来没有涉及：“如果两次经过同一个格子，那么该数只加一次的这个条件”，讨论这个条件需要换一个例子，以DP[6,2,2]为例：DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到达，但由于i = j，也就是2次走到同一个格子，那么数值只能加1次。

    其中W[s,i]表示经过s步后，处于i位置，位置i对应的方格中的数字。下一节我们将根据上述DP方程编码实现。

第三十五章、完美洗牌算法

    题目来源：此题是去年2013年UC的校招笔试题，看似简单，按照题目所要排序后的字符串蛮力变化即可，但若要完美的达到题目所要求的时空复杂度，则需要我们花费不小的精力。OK，请看下文详解，一步步优化。

    题目要我们怎么变换，咱们就怎么变换。此题@陈利人也分析过，在此，引用他的思路进行说明。为了便于分析，我们取n=4，那么题目要求我们把

仔细观察变换前后两个序列的特点，我们可做如下一系列操作：

  第①步、确定b1的位置，即让b1跟它前面的a2，a3，a4交换：

  第②步、接着确定b2的位置，即让b2跟它前面的a3，a4交换：

  第③步、b3跟它前面的a4交换位置：

   b4已在最后的位置，不需要再交换。如此，经过上述3个步骤后，得到我们最后想要的序列。但此方法的时间复杂度为O（N^2），我们得继续寻找其它方法，看看有无办法能达到题目所预期的O（N）的时间复杂度。

当然，除了如上面所述的让b1，b2，b3，b4步步前移跟它们各自前面的元素进行交换外，我们还可以每次让序列中最中间的元素进行交换达到目的。还是用上面的例子，针对a1，a2，a3，a4，b1，b2，b3，b4

  第①步：交换最中间的两个元素a4，b1，序列变成（待交换的元素用粗体表示）：

  第②步，让最中间的两对元素各自交换：

  第③步，交换最中间的三对元素，序列变成：

  同样，此法同解法1.1、步步前移一样，时间复杂度依然为O（N^2），我们得下点力气了。

    玩过扑克牌的朋友都知道，在一局完了之后洗牌，洗牌人会习惯性的把整副牌大致分为两半，两手各拿一半对着对着交叉洗牌，如下图所示：

    这个算法解决一个什么问题呢？跟本题有什么联系呢？

   Yeah，顾名思义，完美洗牌算法解决的就是一个完美洗牌问题。什么是完美洗牌问题呢？即给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,...bn,an。读者可以看到，这个完美洗牌问题本质上与本题完全一致，只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可。

通过完美洗牌问题，得到：

再让上面相邻的元素两两swap，即可达到本题的要求：

    也就是说，如果我们能通过完美洗牌算法（时间复杂度O(N)，空间复杂度O(1)）解决了完美洗牌问题，也就间接解决了本题。

    虽然网上已有不少文章对上篇论文或翻译或做解释说明，但对于初学者来说，理解难度实在太大，再者，若直接翻译原文，根本无法看出这个算法怎么一步步得来的，故下文将从完美洗牌算法的最基本的原型开始说起，以让读者能对此算法一目了然。

   为方便讨论，我们设定数组的下标从1开始，下标范围是[1..2n]。 还是通过之前n=4的例子，来看下每个元素最终去了什么地方。

  那么推广到一般情况即是：前n个元素中，第i个元素去了 第（2 * i）的位置。

  上面是针对前n个元素，那么针对后n个元素，可以看出：

    熟悉分治法的朋友，包括若看了此文的读者肯定知道，当一个问题规模比较大时，则大而化小，分而治之。对于本题，假设n是偶数，我们试着把数组从中间拆分成两半(为了方便描述，只看数组下标就够了)：

  换言之，当n是偶数的时候，我们把原问题拆分成了A，B两个子问题，继而原n的求解转换成了n‘ = n/2 的求解。

  可当n是奇数的时候呢？我们可以把前半段多出来的那个元素a先拿出来放到末尾，后面所有元素前移，于此，新数列的最后两个元素满足已满足要求，只需考虑前2*(n-1)个元素即可，继而转换成了n-1的问题。

  针对上述n分别为偶数和奇数的情况，下面举n=4和n=5两个例子来说明下。

    按照之前n为偶数时的思路，把前半段的后2个元素a3 a4同后半段的前2个元素b1 b2交换，可得：

   还是按照之前n为奇数时的思路，先把a5先单独拎出来放在最后，然后所有剩下的元素全部前移，变为：

  此时，最后的两个元素b5 a5已经是我们想要的结果，只要跟之前n=4的情况一样考虑即可。

    故事实上，当我们采用分治算法的时候，其时间复杂度的计算公式为： T(n) = 2*T(n / 2) + O(n)  ，这个就是跟归并排序一样的复杂度式子，由《算法导论》中文第二版44页的主定理，可最终解得T(n) = O(nlogn)。至于空间，此算法在数组内部折腾的，所以是O(1)（在不考虑递归的栈的空间的前提下）。

  因为之前无论是perfect_shuffle1，还是perfect_shuffle2，这两个算法的均未达到时间复杂度O（N）并且空间复杂度O（1）的要求，所以我们必须得再找一种新的方法，以期能完美的解决本节开头提出的完美洗牌问题。

   让我们先来回顾一下2.1节位置置换perfect_shuffle1算法，还记得我之前提醒读者的关于当n=4时，通过位置置换让每一个元素到了最后的位置时，所形成的两个圈么？我引用下2.1节的相关内容：

    即通过置换，我们得到如下结论：

  “于此同时，我也提醒下读者，根据上面变换的节奏，我们可以看出有两个圈，

    因此我们只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的，且因为圈与圈是不想交的，所以这样下来，我们刚好走了O（N）步。

//数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
 
 
 

    也就是说，利用上述这个结论，我们可以解决这种特殊长度2*n = （3^k-1）的数组问题，那么若给定的长度n是任意的咋办呢？此时，我们可以借鉴2.2节、分而治之算法的思想，把整个数组一分为二，即拆分成两个部分：

• 让一部分的长度满足神级结论：若2*m = （3^k-1），则恰好k个圈，且每个圈头部的起始位置分别是1,3,9，...3^(k-1)。其中m<n，m往神级结论所需的值上套；
• 剩下的n-m部分单独计算；

    当把n分解成m和n-m两部分后，原始数组对应的下标如下（为了方便描述，我们依然只需要看数组下标就够了）：

   参照之前2.2节、分而治之算法的思路，且更为了能让前部分的序列满足神级结论2*m = （3^k-1），我们可以把中间那两段长度为n-m和m的段交换位置，即相当于把m+1..n，n+1..n+m的段循环右移m次（为什么要这么做？因为如此操作后，数组的前部分的长度为2m，而根据神级结论：当2m=3^k-1时，可知这长度2m的部分恰好有k个圈）。

  而如果读者看过本系列第一章、左旋转字符串的话，就应该意识到循环位移是有O（N）的算法的，其思想即是把前n-m个元素（m+1.. n）和后m个元素（n+1 .. n+m）先各自翻转一下，再将整个段（m+1.. n，

  这个翻转的代码如下：

    翻转后，得到的目标数组的下标为：

    OK，理论讲清楚了，再举个例子便会更加一目了然。当给定n=7时，若要满足神级结论2*n=3^k-1，k只能取2，继而推得n‘=m=4。

    既然m=4，即让上述数组中有下划线的两个部分交换，得到：

    从上文的分析过程中也就得出了我们的完美洗牌算法，其算法流程为：

    上述算法流程对应的论文原文为：

    以上各个步骤对应的时间复杂度分析如下：

1. 因为循环不断乘3的，所以时间复杂度O(logn)
2. 每个圈，每个元素只走了一次，一共2*m个元素，所以复杂度omega(m), 而m < n，所以 也在O(n)内。

   此完美洗牌算法实现的参考代码如下：

    啊哈！以上代码即解决了完美洗牌问题，那么针对本章要解决的其变形问题呢？是的，如本章开头所说，在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可，代码如下：

  上述的这个“在完美洗牌问题的基础上对它最后的序列swap两两相邻元素”的操作（当然，你也可以让原数组第一个和最后一个不变，中间的2 * (n - 1)项用原始的标准完美洗牌算法做），只是在完美洗牌问题时间复杂度O(N)空间复杂度O(1)的基础上再增加O(N)的时间复杂度，故总的时间复杂度O(N)不变，且理所当然的保持了空间复杂度O(1)。至此，咱们的问题得到了圆满解决！

2.3.5、神级结论是如何来的？

    我们的问题得到了解决，但本章尚未完，即决定完美洗牌算法的神级结论：若2*n=（3^k - 1），则恰好只有k个圈，且每个圈头部的起始位置分别是1,3,9，...3^(k-1)，是如何来的呢？

    要证明这个结论的关键就是：这所有的圈合并起来必须包含从1到M之间的所有证书，一个都不能少。这个证明有点麻烦，因为证明过程中会涉及到等数论知识，但再远的路一步步走也能到达。

    首先，让咱们明确以下相关的概念，定理，及定义（搞清楚了这些东西，咱们便证明了一大半）：

换言之，若定义为整数，假设/N定义为整数Z除以N后全部余数的集合，包括{0...N-1}等N个数，而（/N)*则定义为这Z/N中{0...N-1}这N个余数内与N互质的数集合。

• 取头为3，就可以得到｛3,6,12,24,21,15｝，这就是以3为头的环，这个圈的特点是所有的数都是3的倍数，且都不是9的倍数。为什么呢？因为2^k和27互素。

• 取9为头，这就很简单了，这个圈就是｛9,18}
  

     你会发现，小于27的所有自然数，要么在第一个圈里面，也就是那些和27互素的数；要么在第二个圈里面，也就是那些是3的倍数，但不是9的倍数的数；要么在第三个圈里面，也就是是9倍数的数，而之所以能够这么做，就是因为2是27的本原根。证明完毕。

    最后，咱们也再验证下上述过程：

2.3.6、完美洗牌问题的几个扩展

    至此，本章开头提出的问题解决了，完美洗牌算法的证明也证完了，是否可以止步了呢？OH，NO！读者有无思考过下述问题：

1. 完美洗牌问题是两手洗牌，假设有三只手同时洗牌呢？那么问题将变成：输入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN，要求输出是c1,b1,a1,c2,b2,a2,……cN,bN,aN，这个时候，怎么处理？

    以上两个完美洗牌问题的几个扩展请读者思考，具体解答请参看参考链接第15条。

    以上第35章可能是整个系列迄今为止我最满意的一篇，不仅仅是因为此章思路清晰，过渡自然，代码风格良好，更因为有了@曹鹏博士 的加入，编程艺术如虎添翼，质量更上一层！

    :编程艺术通过解决一个个实际的编程面试题，让广大初学者一步步学会分析问题解决问题优化问题的能力，且每个问题的讲解足够通俗，希望后续我(们)做得越来越好！July、二零一三年八月二十四日凌晨零点三十七分。