一些C語言中字符串的算法問題解決實例小結

更新時間：2016年03月15日 16:09:07 作者：wuzhekai1985

這篇文章主要介紹了一些C語言中字符串的算法問題解決實例小結,包括將字符串轉化為int類型的數(shù)及旋轉字符串等操作,需要的朋友可以參考下

    字符串問題是面試中經(jīng)常出現(xiàn)的問題，這類問題有很多，難以不一。下面是幾道字符串的題目，網(wǎng)上都能找到解答，自己實現(xiàn)了一下，供網(wǎng)友參考。感覺算法重要的是要有正確的思路，實現(xiàn)起來不是問題。自己一定要多思考，這樣收獲可能會更多一點。

問題1：找兩個字符串的最長公共子串。
        具體描述，如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
    思路：算法書上一般都有介紹，就是用動態(tài)規(guī)劃的思想。關鍵是要找到最優(yōu)子結構性質，這一點比較難。另外一個經(jīng)常問到的問題“求子數(shù)組的最大和”，用的也是動態(tài)規(guī)劃的思想。找兩個字符串最長公共子串的核心就是找最優(yōu)子結構。
        設序列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}
      有了上述關系，則很容易得到遞推的式子。用一個二維數(shù)組 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]}
        基本上差不多了，但是題目要求打印最長公共子串，只要用一個數(shù)組R記錄得到最長公共子串的過程，其中R[i][j]表示Z[i][j]的值是由哪個子問題的解得到的。
       參考代碼：

//函數(shù)功能 ： 打印最長公共子串 
//函數(shù)參數(shù) ： 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; 
} 
//函數(shù)功能 ： 求兩個字符串的最大公共子串 
//函數(shù)參數(shù) ： 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)。如果能聯(lián)想到散列，那么很容易就能給出下面的解法，相信很多人都能想到。需要一個256字節(jié)的數(shù)組，記錄第二個字符串中每個字符的出現(xiàn)情況，0表示未出現(xiàn)，1表示出現(xiàn)。然后遍歷第一個字符串，針對每個字符，去查詢記錄數(shù)組，以決定刪除與否。
   參考代碼：

//函數(shù)功能 ： 在字符串中刪除特定字符 
//函數(shù)參數(shù) ： 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：左旋轉字符串，其實也可以左旋數(shù)組
   具體描述，定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉2位得到字符串cdefab。請實現(xiàn)字符串左旋轉的函數(shù)。要求時間對長度為n的字符串操作的復雜度為O(n)，輔助內存為O(1)。
   思路：用了一個小技巧，如果旋轉的字符串為XY，其中Y是要旋轉到X前面的。只要分別將子字符串 X 和 Y 翻轉，然后再將整個字符串再做一次翻轉即可。STL的一個算法rotate就是用了這個。
   參考代碼：

//函數(shù)功能 ： 將字符串翻轉 
//函數(shù)參數(shù) ： 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--; 
  } 
} 
 
//函數(shù)功能 ： 將字符串左旋 n 位 
//函數(shù)參數(shù) ： pSrc為源字符串，n為左旋位數(shù) 
//返回值 ：  空 
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：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
   思路：這一題不難，因為每個字符只有8位，因此可以用計數(shù)法。首先統(tǒng)計字符串中每個字符的出現(xiàn)次數(shù)，然后從頭遍歷字符串，對于當前字符，查詢統(tǒng)計表，如果出現(xiàn)的次數(shù)為1，則輸出該字符即可。
   參考代碼：

//函數(shù)功能 ： 在一個字符串中找到第一個只出現(xiàn)一次的字符 
//函數(shù)參數(shù) ： pStr為源字符串 
//返回值 ：  目標字符 
char FirstAppearOnce(char *pStr) 
{ 
  if(pStr == NULL) 
    return '\0'; //未找到返回空字符 
 
  int count[256] = {0}; 
  char *pTmp = pStr; 
   
  while(*pTmp != '\0') //統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù) 
  { 
    count[*pTmp]++; 
    pTmp++; 
  } 
  while(*pStr != '\0') //遍歷字符串，找到第一個只出現(xiàn)一次的字符 
  { 
    if(count[*pStr] == 1) 
      break; 
    pStr++; 
  } 
  return *pStr; //找到的字符 
}

問題5：寫一個函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)。功能：在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內存。
        例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789
    思路：這一題比較簡單，掃描一遍字符串即可，遇到數(shù)字時將數(shù)字個數(shù)加1，然后與最長串比較，如果長度大于最長串，更新最長串；遇到非數(shù)字時，將數(shù)字計數(shù)器清零。
    參考代碼：函數(shù)名和形參名修改了一下，個人習慣。

//函數(shù)功能 ： 在字符串中找出連續(xù)最長的數(shù)字串 
//函數(shù)參數(shù) ： pSrc表示源串，pDest記錄最長數(shù)字串的起始位置 
//返回值 ：  最長數(shù)字串的長度 
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') //數(shù)字 
    { 
      cnt++; 
      if(cnt > max) //更新最長的數(shù)字串 
      { 
        pDest = pSrc - cnt + 1; 
        max = cnt; 
      } 
    } 
    else 
      cnt = 0; 
    pSrc++; 
  } 
  if(cnt > max) 
  { 
    pDest = pSrc - cnt + 1; 
    max = cnt; 
  } 
  return max; 
}

問題6：字符串轉換為整數(shù)
      問題描述：輸入一個表示整數(shù)的字符串，把該字符串轉換成整數(shù)并輸出。例如輸入字符串"345"，則輸出整數(shù)345。
       思路：轉換的過程比較簡單，每次讀入一個字符，將之前保存的值乘以10，然后再加上這個字符表示的數(shù)字。這是正常情況。這個問題主要是考察各種不正常情況的處理。假設函數(shù)的聲明為 int StrToInt(const char *str);
       （1）輸入的字符串指針為空；
       （2）數(shù)字前面有正負號的處理；
       （3）字符串表示的數(shù)字超過了32位整數(shù)能表示的范圍，即溢出處理；
       （4）輸入了非法字符，即除了數(shù)字及正負號的其他字符；
       （5）以字符' 0 '開始的串，' 0 '后面還跟了其他字符，也是非法的。
        如果能很好的處理這些情況，那么程序的健壯性大大增強。其中有兩種情況處理起來有點麻煩，第一，如何處理溢出，我們可以使用std::numeric_limits<int>::max()，可以定義一個long long的變量，然后與這個最大值相比，從而判斷是否溢出了。第二。由于返回值為一個整型數(shù)，那么如果轉換失敗，返回什么呢？如果是'0 ' ，那么就無法區(qū)分正常輸入"0"的情況。兩種方案，修改函數(shù)聲明，通過返回值表明轉換的成功與否，或者定義一個全局變量，用來保存轉換的成功與否。參考代碼中使用了第二種方案。
        參考代碼：先給出的是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;  //負數(shù)標記  
  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;  
}

您可能感興趣的文章: