字符串問(wèn)題是面試中經(jīng)常出現(xiàn)的問(wèn)題，這類問(wèn)題有很多，難以不一。下面是幾道字符串的題目，網(wǎng)上都能找到解答，自己實(shí)現(xiàn)了一下，供網(wǎng)友參考。感覺(jué)算法重要的是要有正確的思路，實(shí)現(xiàn)起來(lái)不是問(wèn)題。自己一定要多思考，這樣收獲可能會(huì)更多一點(diǎn)。
問(wèn)題1：找兩個(gè)字符串的最長(zhǎng)公共子串。
具體描述，如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫(xiě)一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
思路：算法書(shū)上一般都有介紹，就是用動(dòng)態(tài)規(guī)劃的思想。關(guān)鍵是要找到最優(yōu)子結(jié)構(gòu)性質(zhì)，這一點(diǎn)比較難。另外一個(gè)經(jīng)常問(wèn)到的問(wèn)題“求子數(shù)組的最大和”，用的也是動(dòng)態(tài)規(guī)劃的思想。找兩個(gè)字符串最長(zhǎng)公共子串的核心就是找最優(yōu)子結(jié)構(gòu)。
設(shè)序列X = {x1,x2,…xm}和Y = {y1,y2,…yn}的最長(zhǎng)公共子串為Z = {z1,z2,…zk},則
1 若xm= yn且zk=xm=yn, 則Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子串
2 若xm!=yn且zk!=xm，則Z是Xm-1和Y的最長(zhǎng)公共子串
3 若xm!=yn且zk!=yn，則Z是X和Yn-1的最長(zhǎng)公共子串
其中Xm-1= {x1,x2,…,xm-1},Yn-1 = {y1,y2,…,yn-1}Zk-1 = {z1,z2,…zk-1}
有了上述關(guān)系，則很容易得到遞推的式子。用一個(gè)二維數(shù)組 R 記錄結(jié)果，其中Z[i][j]表示Xi和Yj的最長(zhǎng)公共子串長(zhǎng)度。
（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]}
基本上差不多了，但是題目要求打印最長(zhǎng)公共子串，只要用一個(gè)數(shù)組R記錄得到最長(zhǎng)公共子串的過(guò)程，其中R[i][j]表示Z[i][j]的值是由哪個(gè)子問(wèn)題的解得到的。
參考代碼：
//函數(shù)功能 ： 打印最長(zhǎng)公共子串 //函數(shù)參數(shù) ： X為源字符串1，Y為源字符串2，R為記錄的過(guò)程，row為R的行坐標(biāo)，col為R的列坐標(biāo) //返回值 ： 空 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ù)功能 ： 求兩個(gè)字符串的最大公共子串 //函數(shù)參數(shù) ： X為源字符串1，Y為源字符串2 //返回值 ： 最大長(zhǎng)度 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; } } //開(kāi)始計(jì)算 for(i = 1; i <=lenX; i++) { for(j = 1; j <=lenY; j++) { if(X[i-1] == Y[j-1]) //字符串的下標(biāo)從0開(kāi)始，所以減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得到 } } } } //打印最長(zhǎng)公共子串 LCS_Print(X, Y, R, lenX, lenY); //記錄最大長(zhǎng)度 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; }
問(wèn)題2：在字符串中刪除特定元素
具體描述，輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。
思路：這是字符查找的一個(gè)問(wèn)題，最簡(jiǎn)單的就是考察第二個(gè)字符串的每個(gè)字符，然后檢查第一個(gè)字符串中有沒(méi)有這個(gè)字符，有的話刪除。這樣的時(shí)間復(fù)雜度是O(mn)。對(duì)于查找，我們?nèi)菀紫氲蕉植檎摇⑸⒘羞@些概念。散列的查找是非常快，時(shí)間復(fù)雜度為O(1)。如果能聯(lián)想到散列，那么很容易就能給出下面的解法，相信很多人都能想到。需要一個(gè)256字節(jié)的數(shù)組，記錄第二個(gè)字符串中每個(gè)字符的出現(xiàn)情況，0表示未出現(xiàn)，1表示出現(xiàn)。然后遍歷第一個(gè)字符串，針對(duì)每個(gè)字符，去查詢記錄數(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; //開(kāi)始刪除 char *pCur = pSrc; while(*pSrc != '/0') { if(hash[*pSrc] == false) //不用刪除 *pCur++ = *pSrc; pSrc++; } *pCur = '/0'; }問(wèn)題3：左旋轉(zhuǎn)字符串，其實(shí)也可以左旋數(shù)組
具體描述，定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時(shí)間對(duì)長(zhǎng)度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
思路：用了一個(gè)小技巧，如果旋轉(zhuǎn)的字符串為XY，其中Y是要旋轉(zhuǎn)到X前面的。只要分別將子字符串 X 和 Y 翻轉(zhuǎn)，然后再將整個(gè)字符串再做一次翻轉(zhuǎn)即可。STL的一個(gè)算法rotate就是用了這個(gè)。
參考代碼：
//函數(shù)功能 ： 將字符串翻轉(zhuǎn) //函數(shù)參數(shù) ： pBegin指向第一個(gè)字符，pEnd指向最后一個(gè)字符 //返回值 ： 空 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); }
問(wèn)題4：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
思路：這一題不難，因?yàn)槊總€(gè)字符只有8位，因此可以用計(jì)數(shù)法。首先統(tǒng)計(jì)字符串中每個(gè)字符的出現(xiàn)次數(shù)，然后從頭遍歷字符串，對(duì)于當(dāng)前字符，查詢統(tǒng)計(jì)表，如果出現(xiàn)的次數(shù)為1，則輸出該字符即可。
參考代碼：
//函數(shù)功能 ： 在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符 //函數(shù)參數(shù) ： pStr為源字符串 //返回值 ： 目標(biāo)字符 char FirstAppearOnce(char *pStr) { if(pStr == NULL) return '/0'; //未找到返回空字符 int count[256] = {0}; char *pTmp = pStr; while(*pTmp != '/0') //統(tǒng)計(jì)字符串中每個(gè)字符出現(xiàn)的次數(shù) { count[*pTmp]++; pTmp++; } while(*pStr != '/0') //遍歷字符串，找到第一個(gè)只出現(xiàn)一次的字符 { if(count[*pStr] == 1) break; pStr++; } return *pStr; //找到的字符 }
問(wèn)題5：寫(xiě)一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)。功能：在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回，并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789
思路：這一題比較簡(jiǎn)單，掃描一遍字符串即可，遇到數(shù)字時(shí)將數(shù)字個(gè)數(shù)加1，然后與最長(zhǎng)串比較，如果長(zhǎng)度大于最長(zhǎng)串，更新最長(zhǎng)串；遇到非數(shù)字時(shí)，將數(shù)字計(jì)數(shù)器清零。
參考代碼：函數(shù)名和形參名修改了一下，個(gè)人習(xí)慣。
//函數(shù)功能 ： 在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串 //函數(shù)參數(shù) ： pSrc表示源串，pDest記錄最長(zhǎng)數(shù)字串的起始位置 //返回值 ： 最長(zhǎng)數(shù)字串的長(zhǎng)度 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) //更新最長(zhǎng)的數(shù)字串 { pDest = pSrc - cnt + 1; max = cnt; } } else cnt = 0; pSrc++; } if(cnt > max) { pDest = pSrc - cnt + 1; max = cnt; } return max; } 問(wèn)題6：字符串轉(zhuǎn)換為整數(shù)
問(wèn)題描述：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。例如輸入字符串"345"，則輸出整數(shù)345。
思路：轉(zhuǎn)換的過(guò)程比較簡(jiǎn)單，每次讀入一個(gè)字符，將之前保存的值乘以10，然后再加上這個(gè)字符表示的數(shù)字。這是正常情況。這個(gè)問(wèn)題主要是考察各種不正常情況的處理。假設(shè)函數(shù)的聲明為 int StrToInt(const char *str);
（1）輸入的字符串指針為空；
（2）數(shù)字前面有正負(fù)號(hào)的處理；
（3）字符串表示的數(shù)字超過(guò)了32位整數(shù)能表示的范圍，即溢出處理；
（4）輸入了非法字符，即除了數(shù)字及正負(fù)號(hào)的其他字符；
（5）以字符' 0 '開(kāi)始的串，' 0 '后面還跟了其他字符，也是非法的。
如果能很好的處理這些情況，那么程序的健壯性大大增強(qiáng)。其中有兩種情況處理起來(lái)有點(diǎn)麻煩，第一，如何處理溢出，我們可以使用std::numeric_limits<int>::max()，可以定義一個(gè)long long的變量，然后與這個(gè)最大值相比，從而判斷是否溢出了。第二。由于返回值為一個(gè)整型數(shù)，那么如果轉(zhuǎn)換失敗，返回什么呢？如果是'0 ' ，那么就無(wú)法區(qū)分正常輸入"0"的情況。兩種方案，修改函數(shù)聲明，通過(guò)返回值表明轉(zhuǎn)換的成功與否，或者定義一個(gè)全局變量，用來(lái)保存轉(zhuǎn)換的成功與否。參考代碼中使用了第二種方案。
參考代碼：先給出的是std::numeric_limits<int>::max()的用法。
#include <iostream> #include <limits> //需包含這個(gè)頭文件 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'開(kāi)始但不是"0" 這條其實(shí)可以忽略 return 0; unsigned i = 0; bool minus = false; //負(fù)數(shù)標(biāo)記 if(str[i] == '-' || str[i] == '+') //判斷是不是以正負(fù)號(hào)開(kāi)始 { minus = (str[i] == '-')? true: false; i++; } long long result = 0; //轉(zhuǎn)換的結(jié)果 while(str[i] != '/0') { char c = str[i++]; if(c >= '0' && c <='9') { result = result * 10 + (c - '0'); if(minus) //負(fù)溢出 { if(result - 1 > numeric_limits<int>::max()) return 0; } else //正溢出 { if(result > numeric_limits<int>::max()) return 0; } } else { return 0; } } strToIntOK = true; //結(jié)果返回 需強(qiáng)制轉(zhuǎn)換一下 return minus? (int)(-result):(int)result; } 新聞熱點(diǎn)
疑難解答
圖片精選
