找工作知识储备(2)---数组字符串那些经典算法：最大子序列和，最长递增子序列，最长公共子串，最长公共子序列，字符串编辑距离，最长不重复子串，最长回文子串

作者：寒小阳

时间：2013年9月。

出处：http://blog.csdn.net/han_xiaoyang/article/details/11969497。
声明：版权所有，转载请注明出处，谢谢。

0、前言

这一部分的内容原本是打算在之后的字符串或者数组专题里面写的，但看着目前火热进行的各家互联网公司笔试面试中，出现了其中的一两个内容，就随即将这些经典问题整理整理，单写一篇发上来了。这里争取覆盖面广一些，列举了7个最经典的问题，也会是之后大家笔试面试常见到的问题，而每个问题下都列举了几种思路，掌握这些经典问题的解题思路和算法相信对同类型问题的解答都能有帮助。

这里总结的几个问题分别是最大子序列和，最长递增子序列，最长公共子串，最长公共子序列，字符串编辑距离，最长不重复子串，最长回文子串。其中前两个问题是针对数组求解的，后五个问题是针对字符串求解的。多数问题都有动态规划的解法（博主不堪地表示，自己动态规划也较弱，只能想到一些基本的思路），这些解法需要细细琢磨，可发散式地使用在很多其他的题目上。

一、最大子序列和

这里把最大子序列和放在第一个位置，它并不是字符串相关的问题，事实上它的目的是要找出由数组成的一维数组中和最大的连续子序列。比如[0，-2，3，5，-1，2]应返回9，[-9，-2，-3，-5，-3]应返回-2。

1、动态规划法

你也许从这两个例子中已经可以看出，使用动态规划的方法很容易完成这个任务，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。但是你可能需要谨慎一些，在整个数组都为负的情况下，所以初始的和最大值赋值不当的话可能会出问题。

根据以上的思路我们可以有以下的代码：

代码如下：
       设有字符串a[0...n]，b[0...m]，字符串a对应的是二维数组num的行，字符串b对应的是二维数组num的列。我们有以下的递推公式：

       我们在程序中，可以使用二维数组flag来记录下标i和j的走向。数字"1"表示，斜向下；数字"2"表示，水平向右；数字"3"表示，竖直向下。这样我们可以求解出行进的路径，从而得到最长公共子序列。代码如下：
1）递归方法(用到动态规划)
           由上述的递归公式可以有以下代码：
    C表示当前的回文中心，L和R处的线表示以C为中心可以到达的最左和最右位置，如果知道这些，我们如何可以更好的计算C后面的P[i]. 
    假设我们当前计算的是 i = 13, 根据对称性，我们知道对称的那个下标 i' = 9. 
根据C对称的原则，我们很容易得到如下数据 P[ 12 ] = P[ 10 ] = 0, P[ 13 ] = P[ 9 ] = 1, P[ 14 ] = P[ 8 ] = 0).
当时当i = 15的时候，却只能得到回文 “a#b#c#b#a”, 长度是5， 而对称 i ' = 7 的长度是7. 
        如上图所示，如果以 i, i' 为中心，画出对称的区域如图，其中以i‘ = 7 对称的区域是 实心绿色 + 虚绿色 和 左侧，虚绿色表示当前的对称长度已经超过之前的对称中心C。而之前的P对称性质成立的原因是 i 右侧剩余的长度 R - i 正好比 以 i‘ 为中心的回文小。 
        这个性质可以这样归纳，对于 i 而言，因为根据C对称的最右是R，所以i的右侧有 R - i 个元素是保证是 i' 左侧是对称的。 而对于 i' 而言他的P值，也就是回文串的长度，可能会比 R-i 要大。 如果大于 R - i, 对于i而言，我们只能暂时的先填写 P[i] = R - i, 然后依据回文的属性来扩充P[i] 的值； 如果P[i '] 小于R-i，那么说明在对称区间C内，i的回文串长度和i' 是一样长的。例如我们的例子中 i = 15, 因为R = 20，所以i右侧 在对称区间剩余的是 R - 15 = 5, 而 i’ = 7 的长度是7. 说明 i' 的回文长度已经超出对称区间。我们只能使得P[i] 赋值为5， 然后尝试扩充P[i]. 
if P[ i' ] ≤ R  i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥R  i. (这里下一步操作是扩充 P[ i ].
       扩充P[i] 之后，我们还要做一件事情是更新 R 和 C， 如果当前对称中心的最右延伸大于R，我们就更新C和R。在迭代的过程中，我们试探i的时候，如果P[i'] <= R - i, 那么只要做一件事情。 如果不成立我们对当前P[i] 做扩展，因为最大长度是n，扩展最多就做n次，所以最多做2*n。 所以最后算法复杂度是 O(n)
       具体实现的代码如下：

// 转换S 到 T.// 例如, S = "abba", T = "^#a#b#b#a#$".// ^ 和 $ 作为哨兵标记加到两端以避免边界检查string preProcess(string s) {  int n = s.length();  if (n == 0) return "^$";  string ret = "^";  for (int i = 0; i < n; i++)    ret += "#" + s.substr(i, 1);   ret += "#$";  return ret;} string longestPalindrome(string s) {  string T = preProcess(s);  int n = T.length();  int *P = new int[n];  int C = 0, R = 0;  for (int i = 1; i < n-1; i++) {    int i_mirror = 2*C-i; // equals to i' = C - (i-C)     P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;     // Attempt to expand palindrome centered at i    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])      P[i]++;     // If palindrome centered at i expand past R,    // adjust center based on expanded palindrome.    if (i + P[i] > R) {      C = i;      R = i + P[i];    }  }   // Find the maximum element in P.  int maxLen = 0;  int centerIndex = 0;  for (int i = 1; i < n-1; i++) {    if (P[i] > maxLen) {      maxLen = P[i];      centerIndex = i;    }  }  delete[] P;   return s.substr((centerIndex - 1 - maxLen)/2, maxLen);}


2楼vince_n3天前 22:56
楼主厉害。请问一下楼主使用什么绘图工具啊，绘图做得这么漂亮
1楼heyu19923123天前 13:14
楼主真心牛，代码水平让我等望其项背呀，希望可以向楼主学习学习
Re: yaoqiang20113天前 13:48
回复heyu1992312n过奖了，我们都是学习者，互相学习！