程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 面試題3：替換空格和清除空格

面試題3：替換空格和清除空格

編輯：C++入門知識

一、替換空格

請實現一個函數，把字符串中的每個空格替換成“%20”。例如輸入“We are happy.",則輸出”We%20are%20happy."

分析：在空間復雜度盡可能低的情況下，不允許開辟一個新的數組來存放替換空格後的字符串。如果從前往後替換字符串，那麼保存在空格後面的字符串肯定會被覆蓋。假設字符串的長度為n。對每個空格字符，需要移動後面O(n)個字符，因此對含有O(n)個空格字符的字符串而言總的時間復雜度是O(n^2)，明顯不可取。

思路：我們考慮從後往前進行替換，時間復雜度降為O(n)。

（1）首先遍歷一遍字符串，找出字符串的長度以及其中的空格數

（2）根據原字符串的長度和空格數求出最後新的字符串的長度

（3）設置兩個指針分別指向原字符串和新字符串的末尾位置

（4）如果原字符串的指針指向的內容不空，則將內容賦值給新指針指向的位置；否則從新指針開始向前賦值“02%”

（5）直到兩個指針相等時表明字符串中的所有空格已經替換完畢

C++代碼：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
//將字符串str中的空格替換為"%20"   
void ReplaceBlank(char *str)  
{  
   int nOldLength = strlen(str);//計算字符串的長度   
  
   //遍歷字符串，求出其中空格的個數   
   int nCountOfBlank = 0;  
   char *p = str;  
   while (*p != '\0')  
   {  
       if (*p == ' ')  
       {  
           ++nCountOfBlank;  
       }  
       ++p;  
   }  
  
   int nNewLength = nOldLength + nCountOfBlank * 2;//新字符串的長度   
   int nOldIndex = nOldLength - 1;  
   int nNewIndex = nNewLength - 1;  
     
   while(nOldIndex != nNewIndex)  
   {  
       if (str[nOldIndex] != ' ')  
       {  
           str[nNewIndex--] = str[nOldIndex];  
       }  
       else  
       {  
           str[nNewIndex--] = '0';  
           str[nNewIndex--] = '2';  
           str[nNewIndex--] = '%';  
       }  
       --nOldIndex;  
   }     
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    char str1[50] = "We are happy.";  
    ReplaceBlank(str1);  
    cout << str1 << endl;  
  
    char str2[50] = "   We are happy.    ";  
    ReplaceBlank(str2);  
    cout << str2 << endl;  
  
    char str3[50] = "";  
    ReplaceBlank(str3);  
    cout << str3 << endl;  
  
    char str4[50] = "    ";  
    ReplaceBlank(str4);  
    cout << str4 << endl;  
  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

//將字符串str中的空格替換為"%20"
void ReplaceBlank(char *str)
{
   int nOldLength = strlen(str);//計算字符串的長度

   //遍歷字符串，求出其中空格的個數
   int nCountOfBlank = 0;
   char *p = str;
   while (*p != '\0')
   {
	   if (*p == ' ')
	   {
		   ++nCountOfBlank;
	   }
	   ++p;
   }

   int nNewLength = nOldLength + nCountOfBlank * 2;//新字符串的長度
   int nOldIndex = nOldLength - 1;
   int nNewIndex = nNewLength - 1;
   
   while(nOldIndex != nNewIndex)
   {
	   if (str[nOldIndex] != ' ')
	   {
		   str[nNewIndex--] = str[nOldIndex];
	   }
	   else
	   {
		   str[nNewIndex--] = '0';
		   str[nNewIndex--] = '2';
		   str[nNewIndex--] = '%';
	   }
	   --nOldIndex;
   }   
}

int _tmain(int argc, _TCHAR* argv[])
{
	char str1[50] = "We are happy.";
	ReplaceBlank(str1);
	cout << str1 << endl;

	char str2[50] = "   We are happy.    ";
	ReplaceBlank(str2);
	cout << str2 << endl;

	char str3[50] = "";
	ReplaceBlank(str3);
	cout << str3 << endl;

	char str4[50] = "    ";
	ReplaceBlank(str4);
	cout << str4 << endl;

	system("pause");
	return 0;
}

二、清除空格

請事先一個函數，把字符串中的每個空格清除。例如輸入“We are happy.",則輸出”Wearehappy."

分析：較為簡單，直接從頭到尾進行清除。

（1）設置兩個指針p1和p2初始狀態都指向字符串的首字符

（2）若p2指向的元素不空，則將p2指向的內容賦給p1,然後都指向下一個元素；否則為空格，則p2指向下一元素。

（3）直到p2指向字符串末尾“\0”時清除空格結束。

C++代碼：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
//清除字符串str中的空格,從前往後遍歷   
void DeleteBlank(char *str)  
{  
    if (str == NULL)  
    {  
        return;  
    }  
  
    char *p1 = str;  
    char *p2 = str;  
  
    while (*p1 != '\0')//注意此處應該是p1,不是p2,因為'\0'仍然需要賦給p1   
    {  
       if (*p2 != ' ')  
       {  
           *(p1++) = *(p2++);  
       }  
       else  
       {  
           p2++;  
       }  
    }     
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    char str1[50] = "We are happy.";  
    DeleteBlank(str1);  
    cout << str1 << endl;  
  
    char str2[50] = "   We are happy.    ";  
    DeleteBlank(str2);  
    cout << str2 << endl;  
  
    char str3[50] = "";  
    DeleteBlank(str3);  
    cout << str3 << endl;  
  
    char str4[50] = "    ";  
    DeleteBlank(str4);  
    cout << str4 << endl;  
  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

//清除字符串str中的空格,從前往後遍歷
void DeleteBlank(char *str)
{
	if (str == NULL)
	{
		return;
	}

	char *p1 = str;
	char *p2 = str;

	while (*p1 != '\0')//注意此處應該是p1,不是p2,因為'\0'仍然需要賦給p1
	{
       if (*p2 != ' ')
       {
		   *(p1++) = *(p2++);
       }
	   else
	   {
		   p2++;
	   }
	}	
}

int _tmain(int argc, _TCHAR* argv[])
{
	char str1[50] = "We are happy.";
	DeleteBlank(str1);
	cout << str1 << endl;

	char str2[50] = "   We are happy.    ";
	DeleteBlank(str2);
	cout << str2 << endl;

	char str3[50] = "";
	DeleteBlank(str3);
	cout << str3 << endl;

	char str4[50] = "    ";
	DeleteBlank(str4);
	cout << str4 << endl;

	system("pause");
	return 0;
}

三、清除多余空格

給定字符串，刪除開始和結尾處的空格，並將中間的多個連續的空格合並成一個。例如輸入“ We are happy. ”,則輸出“We are happy.”

分析：同樣是從前往後遍歷，但需要定義一個bool變量標記是否保存一個空格。初始化時被設置為fasle，這樣開始階段的空格都不會被保存，當碰到一個非空格字符時，保存該字符，然後將標記設置為true，表示會保存字符串中的第一個空格。經過上述幾步操作，可以保證字符串結尾要麼是空字符，要麼是非空格字符。如果是空格字符，則將其設置為"\0"，如果不為空格字符，則在其後面加上"\0"。

C++代碼：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
//清除字符串str中多余的空格,從前往後遍歷   
void DeleteRedundantBlank(char *str)  
{  
    if (str == NULL)  
    {  
        return;  
    }  
  
    char *p1 = str;  
    char *p2 = str;  
    bool keepBlank = false;//記錄空格是否保存      
  
    while (*p1 != '\0')//注意此處應該是p1,不是p2,因為'\0'仍然需要賦給p1   
    {         
        if (*p2 != ' ')  
        {  
            *(p1++) = *(p2++);  
            keepBlank = true;  
        }  
        else  
        {  
            if (keepBlank)  
            {  
               *(p1++) = *(p2++);  
               keepBlank = false;  
            }  
            else  
            {  
               p2++;  
            }             
        }         
    }  
  
    int nlen = strlen(str);  
    if (str[nlen - 1] == ' ')  
    {  
        str[nlen - 1] = '\0';  
    }  
    nlen = strlen(str);  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    char str1[50] = "We are happy.";  
    DeleteRedundantBlank(str1);  
    cout << str1 << endl;  
    cout << strlen(str1) << endl;  
  
    char str2[50] = "   We    are    happy.    ";  
    DeleteRedundantBlank(str2);  
    cout << str2 << endl;  
    cout << strlen(str2) << endl;  
  
    char str3[50] = "";  
    DeleteRedundantBlank(str3);  
    cout << str3 << endl;  
  
    char str4[50] = "    ";  
    DeleteRedundantBlank(str4);  
    cout << str4 << endl;  
  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

//清除字符串str中多余的空格,從前往後遍歷
void DeleteRedundantBlank(char *str)
{
	if (str == NULL)
	{
		return;
	}

	char *p1 = str;
	char *p2 = str;
	bool keepBlank = false;//記錄空格是否保存	

	while (*p1 != '\0')//注意此處應該是p1,不是p2,因為'\0'仍然需要賦給p1
	{		
		if (*p2 != ' ')
		{
			*(p1++) = *(p2++);
			keepBlank = true;
		}
		else
		{
			if (keepBlank)
			{
               *(p1++) = *(p2++);
               keepBlank = false;
			}
			else
			{
               p2++;
			}			
		}		
	}

	int nlen = strlen(str);
	if (str[nlen - 1] == ' ')
	{
		str[nlen - 1] = '\0';
	}
	nlen = strlen(str);
}

int _tmain(int argc, _TCHAR* argv[])
{
	char str1[50] = "We are happy.";
	DeleteRedundantBlank(str1);
	cout << str1 << endl;
	cout << strlen(str1) << endl;

	char str2[50] = "   We    are    happy.    ";
	DeleteRedundantBlank(str2);
	cout << str2 << endl;
	cout << strlen(str2) << endl;

	char str3[50] = "";
	DeleteRedundantBlank(str3);
	cout << str3 << endl;

	char str4[50] = "    ";
	DeleteRedundantBlank(str4);
	cout << str4 << endl;

	system("pause");
	return 0;
}