一些C语言中字符串的算法问题解决实例小结

2020-01-26 14:40:45

字体：大中小

来源：转载

供稿：网友

    字符串问题是面试中经常出现的问题，这类问题有很多，难以不一。下面是几道字符串的题目，网上都能找到解答，自己实现了一下，供网友参考。感觉算法重要的是要有正确的思路，实现起来不是问题。自己一定要多思考，这样收获可能会更多一点。

问题1：找两个字符串的最长公共子串。
        具体描述，如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
    思路：算法书上一般都有介绍，就是用动态规划的思想。关键是要找到最优子结构性质，这一点比较难。另外一个经常问到的问题“求子数组的最大和”，用的也是动态规划的思想。找两个字符串最长公共子串的核心就是找最优子结构。
        设序列X = {x1,x2,…xm}和Y = {y1,y2,…yn}的最长公共子串为Z = {z1,z2,…zk},则
        1 若xm= yn且zk=xm=yn, 则Zk-1是Xm-1和Yn-1的最长公共子串
        2 若xm!=yn且zk!=xm，则Z是Xm-1和Y的最长公共子串
        3 若xm!=yn且zk!=yn，则Z是X和Yn-1的最长公共子串
         其中Xm-1= {x1,x2,…,xm-1},Yn-1 = {y1,y2,…,yn-1}Zk-1 = {z1,z2,…zk-1}
      有了上述关系，则很容易得到递推的式子。用一个二维数组 R 记录结果，其中Z[i][j]表示Xi和Yj的最长公共子串长度。
     （1）如果i = 0或j = 0，Z[i][j] = 0
     （2）如果xi和yj相等，Z[i][j] = Z[i-1][j-1] + 1
     （3）如果xi和yj不相等,Z[i][j] = max{Z[i-1][j],Z[i][j-1]}
        基本上差不多了，但是题目要求打印最长公共子串，只要用一个数组R记录得到最长公共子串的过程，其中R[i][j]表示Z[i][j]的值是由哪个子问题的解得到的。
       参考代码：

//函数功能 ： 打印最长公共子串 //函数参数 ： X为源字符串1，Y为源字符串2，R为记录的过程，row为R的行坐标，col为R的列坐标 //返回值 ：  空 void LCS_Print(const char *X, const char *Y, int **R, int row, int col) {   if(R[row][col] == 1)   {     LCS_Print(X, Y, R, row-1, col-1);     cout<<X[row-1];  //由Xi-1和Yj-1，再加上Xi或Yj得到   }   else if(R[row][col] == 2)     LCS_Print(X, Y, R, row-1, col); //由Xi-1和Yj得到   else if(R[row][col] == 3)      LCS_Print(X, Y, R, row, col-1); //由Xi和Yj-1得到   else     return; } //函数功能 ： 求两个字符串的最大公共子串 //函数参数 ： X为源字符串1，Y为源字符串2 //返回值 ：  最大长度 int LCS(const char *X,const char *Y) {   if(X == NULL || Y == NULL)     return 0;    int lenX = strlen(X);   int lenY = strlen(Y);   if(lenX == 0 || lenY == 0)     return 0;    int i, j;   int **C = new int *[lenX+1];   int **R = new int *[lenX+1];    //初始化   for(i = 0; i <= lenX; i++)   {     C[i] = new int [lenY+1];     R[i] = new int [lenY+1];     for(j = 0; j <= lenY; j++)     {       C[i][j] = 0;       R[i][j] = 0;     }   }    //开始计算    for(i = 1; i <=lenX; i++)   {     for(j = 1; j <=lenY; j++)     {       if(X[i-1] == Y[j-1]) //字符串的下标从0开始，所以减1，即X1 = X[0] Y1 = Y[0]       {         C[i][j] = C[i-1][j-1] + 1;         R[i][j] = 1;  //由Xi-1和Yj-1，再加上Xi或Yj得到       }       else       {         if(C[i-1][j] >= C[i][j-1])          {           C[i][j] = C[i-1][j];           R[i][j] = 2;   //由Xi-1和Yj得到         }         else          {           C[i][j] = C[i][j-1];           R[i][j] = 3;   //由Xi和Yj-1得到         }       }     }   }   //打印最长公共子串   LCS_Print(X, Y, R, lenX, lenY);   //记录最大长度   int lcs = C[lenX][lenY];     //释放空间   for(i = 0; i <= lenX; i++)   {     delete [] C[i];     delete [] R[i];   }   delete C;   delete R;   R = C = NULL;   return lcs; }

问题2：在字符串中删除特定元素
    具体描述，输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。
    思路：这是字符查找的一个问题，最简单的就是考察第二个字符串的每个字符，然后检查第一个字符串中有没有这个字符，有的话删除。这样的时间复杂度是O(mn)。对于查找，我们容易想到二分查找、散列这些概念。散列的查找是非常快，时间复杂度为O(1)。如果能联想到散列，那么很容易就能给出下面的解法，相信很多人都能想到。需要一个256字节的数组，记录第二个字符串中每个字符的出现情况，0表示未出现，1表示出现。然后遍历第一个字符串，针对每个字符，去查询记录数组，以决定删除与否。
   参考代码：

//函数功能 ： 在字符串中删除特定字符 //函数参数 ： pSrc为源字符串，pDel为特定字符集 //返回值 ：  空 void DeleteSpecialChars(char *pSrc, char *pDel) {   if(pSrc == NULL || pDel == NULL)     return;   int lenSrc = strlen(pSrc);   int lenDel = strlen(pDel);   if(lenSrc == 0 || lenDel == 0)     return;   bool hash[256] = { false };   for(int i = 0; i < lenDel; i++) //建立删除字符的索引     hash[pDel[i]] = true;   //开始删除   char *pCur = pSrc;   while(*pSrc != '/0')   {     if(hash[*pSrc] == false) //不用删除       *pCur++ = *pSrc;     pSrc++;   }   *pCur = '/0'; }

问题3：左旋转字符串，其实也可以左旋数组
   具体描述，定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。
   思路：用了一个小技巧，如果旋转的字符串为XY，其中Y是要旋转到X前面的。只要分别将子字符串 X 和 Y 翻转，然后再将整个字符串再做一次翻转即可。STL的一个算法rotate就是用了这个。
   参考代码：

//函数功能 ： 将字符串翻转 //函数参数 ： pBegin指向第一个字符，pEnd指向最后一个字符 //返回值 ：  空 void ReverseString(char *pBegin, char *pEnd) {   if(pBegin == NULL || pEnd == NULL)     return;    while(pBegin < pEnd)   {     //交换字符     char tmp = *pBegin;     *pBegin = *pEnd;     *pEnd = tmp;     //往中间靠拢     pBegin++;     pEnd--;   } }  //函数功能 ： 将字符串左旋 n 位 //函数参数 ： pSrc为源字符串，n为左旋位数 //返回值 ：  空 void LeftRotateString(char *pSrc, unsigned n) {   if(pSrc == NULL || n == 0 || n > strlen(pSrc))     return;    int len = strlen(pSrc);   ReverseString(pSrc, pSrc + n - 1);   ReverseString(pSrc + n, pSrc + len - 1);   ReverseString(pSrc, pSrc + len - 1); }

问题4：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
   思路：这一题不难，因为每个字符只有8位，因此可以用计数法。首先统计字符串中每个字符的出现次数，然后从头遍历字符串，对于当前字符，查询统计表，如果出现的次数为1，则输出该字符即可。
   参考代码：

//函数功能 ： 在一个字符串中找到第一个只出现一次的字符 //函数参数 ： pStr为源字符串 //返回值 ：  目标字符 char FirstAppearOnce(char *pStr) {   if(pStr == NULL)     return '/0'; //未找到返回空字符    int count[256] = {0};   char *pTmp = pStr;      while(*pTmp != '/0') //统计字符串中每个字符出现的次数   {     count[*pTmp]++;     pTmp++;   }   while(*pStr != '/0') //遍历字符串，找到第一个只出现一次的字符   {     if(count[*pStr] == 1)       break;     pStr++;   }   return *pStr; //找到的字符 }

问题5：写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)。功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。
        例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，outputstr所指的值为123456789
    思路：这一题比较简单，扫描一遍字符串即可，遇到数字时将数字个数加1，然后与最长串比较，如果长度大于最长串，更新最长串；遇到非数字时，将数字计数器清零。
    参考代码：函数名和形参名修改了一下，个人习惯。

//函数功能 ： 在字符串中找出连续最长的数字串 //函数参数 ： pSrc表示源串，pDest记录最长数字串的起始位置 //返回值 ：  最长数字串的长度 int ContinueMax(char *pSrc,char * &pDest) {   pDest = NULL;   if(pSrc == NULL)     return 0;    int max = 0, cnt = 0;   while(*pSrc != '/0')   {     if(*pSrc >= '0' && *pSrc <= '9') //数字     {       cnt++;       if(cnt > max) //更新最长的数字串       {         pDest = pSrc - cnt + 1;         max = cnt;       }     }     else       cnt = 0;     pSrc++;   }   if(cnt > max)   {     pDest = pSrc - cnt + 1;     max = cnt;   }   return max; }

问题6：字符串转换为整数
      问题描述：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。
       思路：转换的过程比较简单，每次读入一个字符，将之前保存的值乘以10，然后再加上这个字符表示的数字。这是正常情况。这个问题主要是考察各种不正常情况的处理。假设函数的声明为 int StrToInt(const char *str);
       （1）输入的字符串指针为空；
       （2）数字前面有正负号的处理；
       （3）字符串表示的数字超过了32位整数能表示的范围，即溢出处理；
       （4）输入了非法字符，即除了数字及正负号的其他字符；
       （5）以字符' 0 '开始的串，' 0 '后面还跟了其他字符，也是非法的。
        如果能很好的处理这些情况，那么程序的健壮性大大增强。其中有两种情况处理起来有点麻烦，第一，如何处理溢出，我们可以使用std::numeric_limits<int>::max()，可以定义一个long long的变量，然后与这个最大值相比，从而判断是否溢出了。第二。由于返回值为一个整型数，那么如果转换失败，返回什么呢？如果是'0 ' ，那么就无法区分正常输入"0"的情况。两种方案，修改函数声明，通过返回值表明转换的成功与否，或者定义一个全局变量，用来保存转换的成功与否。参考代码中使用了第二种方案。
        参考代码：先给出的是std::numeric_limits<int>::max()的用法。

#include <iostream> #include <limits>  //需包含这个头文件 using namespace std; int main() {   cout << "The maximum value for type float is: "     << numeric_limits<float>::max( )     << endl;   cout << "The maximum value for type double is: "     << numeric_limits<double>::max( )     << endl;   cout << "The maximum value for type int is: "     << numeric_limits<int>::max( )     << endl;   cout << "The maximum value for type short int is: "     << numeric_limits<short int>::max( )     << endl; }       bool strToIntOK; //全局的变量  int StrToInt(const char *str)  {    strToIntOK = false;    if(str == NULL) //空指针      return 0;        if(str[0] == '0' && str[1] != '/0') //以'0'开始但不是"0" 这条其实可以忽略      return 0;        unsigned i = 0;    bool minus = false;  //负数标记    if(str[i] == '-' || str[i] == '+') //判断是不是以正负号开始    {      minus = (str[i] == '-')? true: false;      i++;    }        long long result = 0; //转换的结果    while(str[i] != '/0')    {      char c = str[i++];      if(c >= '0' && c <='9')      {        result = result * 10 + (c - '0');        if(minus) //负溢出       {         if(result - 1 > numeric_limits<int>::max())            return 0;        }       else //正溢出       {         if(result > numeric_limits<int>::max())           return 0;        }     }      else      {        return 0;      }    }    strToIntOK = true;    //结果返回 需强制转换一下    return minus? (int)(-result):(int)result;  }

上一篇：使用C语言求解扑克牌的顺子及n个骰子的点数问题

下一篇：一波C语言二元查找树算法题目解答实例汇总