原地實現(xiàn)字符串中的每個空格替換成"%20"，例如輸入"We are happy"，輸出"We%20are%20happy"
被替換的字符串當(dāng)然不僅僅是空格，上面只是個例子
這是道很好的題目，也是百度面試中的一道題，題目不難，但是問題得考慮全面。這里給出如下實現(xiàn)代碼：

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int findNumberFirst(const char *str, const char *dest, vector<int>& pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int pos = 0;
 int lenStr = strlen(str);
 int lenDest = strlen(dest);

 if (lenStr < lenDest)
 return 0;

 int count = 0;
 while (pos <= lenStr - lenDest)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pvec.push_back(pos);
  pos += lenDest;
  count++;
 }
 else
 {
  pos++;
 }
 }

 return count;
}

int findNumberLast(const char *str, const char *dest, vector<int> &pvec)
{
 if (str == NULL || dest == NULL)
 return 0;

 int strLen = strlen(str);
 int destLen = strlen(dest);

 if (strLen < destLen)
 return 0;

 int pos = 0;
 while (pos <= strLen - destLen)
 {
 if (strncmp(str + pos, dest, strlen(dest)) == 0)
 {
  pos += destLen;
  pvec.push_back(pos - 1);
 }
 else
 {
  pos++;
 }
 
 }

 return pvec.size();
}

void replaceArray(char *str, const char *src, const char *dest)
{
 if (str == NULL || src == NULL || dest == NULL)
 return;

 vector<int> pvec;
 int strLen = strlen(str);
 int srcLen = strlen(src);
 int destLen = strlen(dest);

 if (strLen < srcLen)
 return;

 int posBefore = 0;
 int posAfter = 0;

 if (srcLen < destLen)
 {
 int count = findNumberLast(str, src, pvec);
 if (count <= 0)
  return;
 
 posAfter = strLen + count * (destLen - srcLen) - 1;
 posBefore = strLen - 1;

 while (count > 0 && posBefore >= 0)
 {
  if (pvec[count - 1] == posBefore)
  {
  posAfter -= destLen;
  strncpy(str + posAfter + 1, dest, strlen(dest));
  count--;
  posBefore--;
  }
  else
  {
  str[posAfter--] = str[posBefore--];
  }
 }
 }
 else if (strLen > destLen)
 {
 int count = findNumberFirst(str, src, pvec);
 if (count <= 0)
  return;

 posAfter = 0;
 posBefore = 0;

 int i = 0;
 while (count >= 0 && posBefore < strLen)
 {
  if (count > 0 && pvec[i] == posBefore)
  {
  strncpy(str + posAfter, dest, strlen(dest));
  posAfter += destLen;
  count--;
  posBefore += srcLen;
  i++;
  }
  else
  {
  str[posAfter++] = str[posBefore++];
  }
 }
 str[posAfter] = '\0';
 }
}

void main()
{ 
 char *str = new char[100];
 if (str == NULL)
 return;
 memset(str, '\0', 100);

 const char *src = " ";
 const char *dest = "%20";
//case1: 只有1個空格
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case2: 兩個空格
 strcpy(str, " ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case3: 正常情況
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case3: 空格在前
 strcpy(str, " we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case4: 空格在后
 strcpy(str, "we are happy ");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case4: 沒空格
 strcpy(str, "wearehappy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 replaceArray(str, dest, src);
 cout << "str: " << str << endl;

//case5: 兩邊一樣
 strcpy(str, "we are happy");

 replaceArray(str, src, dest);
 cout << "str: " << str << endl;

 src = "%20";
 assert(dest == "%20");
 replaceArray(str, dest, src);
 cout << "str: " << str << endl;
}

分析上述代碼，很有意思的一個情況是srcLen和destLen或大或小的情形，其邊界條件的判定不一樣。比如we are happy為例子，從后往前拷貝時，count=2。

在count=0時，恰好將最前面的空格替換完成，we則不用重復(fù)拷貝。但是對于從前往后拷貝，當(dāng)count=0時，最后面的happy將不會被拷貝。

希望本文所述實例對大家C++程序算法設(shè)計的學(xué)習(xí)有所幫助。

您可能感興趣的文章: