2015校招笔试面试算法总结之蓝汛笔试 - 推酷

Arron2014 2015-04-22

展开全文

一、递增矩阵问题

问题描述：如下图所示，在一个m*n矩阵中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，按从小到大的顺序打印这个矩阵到一个一维数组中。如图，则应打印出1，2,2,4,4,6,7,8,8,9,9,10,11,12,13,15.

二、无重复的最长子串问题（引用luxiaoxun博客）

问题描述：找到一个字符串中的一个连续子串，这个子串内不能有任何两个字符是相同的，并且这个子串是符合要求的最长的。例如输入'abcbef'，输出'cbef'。

问题求解：方法一：穷举法，使用2重外循环遍历所有的区间，用2重内循环检验子串是否符合“无重复字符”这一要求。其中外层循环i、j 遍历所有的下标，m、n是内层循环，检查区间[i,j]是否符合要求。空间复杂度是O(1)，时间复杂度O(N^4)。

//O(N^4)的时间复杂度  int max_unique_substring1(char * str)  {    int maxlen = 0;    int begin = 0;    int n = strlen(str);    for(int i=0; i<n; ++i)      for(int j=1; j<n; ++j)      {        int flag = 0;        for(int m=i; m<=j; ++m)        {          for(int n=m+1; n<j; ++n)          {            if(str[n] == str[m])            {              flag = 1;              break;            }          }          if(flag == 1) break;        }        if(flag==0 && j-i+1>maxlen)        {          maxlen = j-i+1;          begin = i;        }      }    printf('%.*s\n', maxlen, &str[begin]);    return maxlen;  }

方法二：对方法一的检验子串是否“无重复字符”进行改进，使用hash表记录字符是否出现过。

//O(N^2)的时间复杂度  int max_unique_substring2(char * str)   {    int i,j;    int begin;    int maxlen = 0;    int hash[256];    int n = strlen(str);    for(i=0; i<n; ++i)    {      memset(hash,0,sizeof(hash));       hash[str[i]] = 1;      for(j=i+1; j<n; ++j)      {        if(hash[str[j]] == 0)          hash[str[j]] = 1;        else          break;      }      if(j-i > maxlen)      {        maxlen = j-i;        begin = i;      }    }    printf('%.*s\n', maxlen, &str[begin]);    return maxlen;  }

方法三：对于字符串'axbdebpqawuva'，构造下表：

表中，字符串有3个‘a’，有2个‘b’，其余为单一字符。next[]记录了下一个与之重复的字符的位置，如str[0]=str[8]=str[12]=‘a’，这时next[0]=8，next[8]=12，next[12]=13，其余同理。值得注意的是，对于没有重复字符的，next[]存储字符结束符‘\0’的下标，即13。

这里，first[i]表示i之后，第一次出现重复字符的那个位置。例如，str[0]之后，第一次出现的重复字符是str[5]=‘b’，当然，从str[1]，str[2]开始也是一样。而从str[3]开始，要到str[12]才出现重复字符‘a’。可以证明，从str[i]起的最长符合要求的长度为first[i]-i，区间为[i,first[i]-1]由此得解。上述最长串是当i=3时，first[i]-i=12-3=9。结果串为debpqawuv。

//O(N)的时间复杂度  int max_unique_substring3(char * str)   {    int maxlen = 0;    int begin = 0;    int n = strlen(str);    int * next = (int*)malloc(sizeof(int)*n); //next[i]记录了下一个与str[i]重复的字符的位置    int * first = (int*)malloc(sizeof(int)*(n+1)); //first[i]记录str[i]后面最近的一个重复点    int hash[256];    memset(hash,n,sizeof(hash));      first[n] = n;    for(int i=n-1; i>=0; i--)    {      next[i] = hash[str[i]];      hash[str[i]] = i;      if (next[i] < first[i+1])        first[i] = next[i];      else        first[i] = first[i+1]; //生成first[]表，复杂度是O(N)的    }    for(int i=0; i<n; i++)    {      if (first[i]-i > maxlen)      {        maxlen = first[i]-i;        begin = i;      }    }    free(first);    free(next);    printf('%.*s\n', maxlen, &str[begin]);    return maxlen;  }

方法四：使用后缀数组

对这个字符串构造后缀数组，在每个后缀数组中，寻找没有重复字符的最长前缀，最长的前缀就是要找的子串

//得到字符串最长的无重复的前缀长度  int longestlen(char * p)  {    int hash[256];    int len = 0;    memset(hash,0,sizeof(hash));    while (*p && !hash[*p])    {      hash[*p] = 1;      ++ len;      ++ p;    }    return len;  }    //使用后缀数组解法  int max_unique_substring4(char * str)  {    int maxlen = -1;    int begin = 0;    char *a[99999];    int n = 0;    while(*str != '\0')    {      a[n++] = str++;    }    for (int i=0; i<n; i++)    {      int temlen = longestlen(a[i]);      if (temlen > maxlen)      {        maxlen = temlen;        begin = i;      }    }    printf('%.*s\n', maxlen, a[begin]);    return maxlen;  }

方法五：DP方案等参考http://www./archives/123.html

三、字符串交错问题

问题描述：判断字符串c是否是字符串a和字符串b按顺序的交错(interleave)。什么叫interleave？是将两个字符串完整的交错在一起，拆分开以后还会是原来的a和b串。

问题分析：一个直观的错觉：把C字符串中的A挑出来，剩下的部分如果是B，这样就说明C是interleave。

这样会遇到一个错误，比如a='aa', b='ab', c='aaba'。如果从c中把A挑出来，会直接挑出开始的'aa'，然后剩余的部分'ba'不等于b字符串，就会做出“不是interleave”的错误判断。这样的错误是由于a、b两个字符串中有共有的字符所导致的挑拣时的错误。

情况一：如果输入字符串a、b中没有共有的字符，那么各挑各的，挑到就一定是属于自己的。如果挑完之后c还有剩余、或者挑不完c就没了，说明c不是interleave。

情况二：如果输入字符串a、b中是有共有字符的，那么各挑各的，很有可能发生挑选错误，把不该挑走的挑走。想要避免这个错误，当遇到共有字符时（即，两方都能要的字符），分别把两种情况都考虑。

下面是解决问题的两种方向。

1、递归方法：由外向里（由大向小）解决问题。

2、DP方法：由里向外（由小向大）解决问题。

递归子问题方法：

对于目标问题(s1, s2, s3)来说，递归子问题是(s1.substr(1), s2, s3.substr(1))和(s1, s2.substr(1), s3.substr(1))两个。

class Solution {  public:    bool isInterleave(string s1, string s2, string s3) {      bool r1 = false, r2 = false;            if(s1 == '' && s2 == '' && s3 == '')        return true;      if(s1 != '' && s3 != '' && s1[0] == s3[0])        r1 = isInterleave(s1.substr(1), s2, s3.substr(1));      if(s2 != '' && s3 != '' && s2[0] == s3[0])        r2 = isInterleave(s1, s2.substr(1), s3.substr(1));      return r1 || r2;    }  };

动态规划方法：

国际惯例，首先找子问题，设计子问题状态量。

对于目标问题(s1, s2, s3)来说，子问题是(s1的前i个字符，s2的前j个字符，s3的前i+j个字符)。

设子问题状态量C[i][j]，其表示，问题(s1的前i个字符，s2的前j个字符，s3的前i+j个字符)的状态（true或false）。那么C[s1.length()][s2.length()]就是目标问题的状态。

初始问题状态C[0][0]=true。

状态递推关系为: C[i][j] = ( (s1[i-1] == s3[i+j-1]) && C[i-1][j] ) || ( (s2[j-1] == s3[i+j-1]) && C[i][j-1] )

代码：

class Solution {  public:  bool isInterleave(string s1, string s2, string s3) {    size_t len1, len2;    len1 = s1.length();    len2 = s2.length();    if(len1 + len2 != s3.length())      return false;        bool **C = new bool*[len1+1]; //注意*在中间    for(int i=0;i<len1+1;i++)      C[i] = new bool[len2+1];        C[0][0] = true;    for(int i=1;i<len1+1;i++)      C[i][0] = (s1[i-1] == s3[i-1]) && C[i-1][0];        for(int j=1;j<len2+1;j++)      C[0][j] = (s2[j-1] == s3[j-1]) && C[0][j-1];        for(int i=1;i<len1+1;i++)      for(int j=1;j<len2+1;j++)        C[i][j] = ( (s1[i-1] == s3[i+j-1]) && C[i-1][j] ) || ( (s2[j-1] == s3[i+j-1]) && C[i][j-1] );        bool result = C[len1][len2];        for(int i=0;i<len1+1;i++)      delete []C[i];    delete []C;    return result;  }    };