剑指offer五：字符串之替换空格

字符串是由若干字符组成的序列，C/C++中每个字符都以字符'\0'作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串中都有一个额外字符的开销，稍不留神就会造成字符串的越界。比如下面的代码：

char str[10];
strcpy(str,"0123456789");

我们先声明一个长度为10的字符数组，然后把字符串“0123456789”复制到数组中。“0123456789”这个字符看起来只有10个字符，但实际上它的末尾还有一个'\0'字符，因此它的实际长度为11个字节。要正确复制该字符串，至少需要一个长度为11个字节的数组。

为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针指向同一个常量字符串时，它们实际上会指向相同的内存地址。但用常量内存初始化数组，情况却有所不同。下面通过一个面试题来学习这一知识点。运行下面的代码，得到的结果是什么？

 

 

替换空格

 

 

 

 

 

#include <iostream>
using namespace std;
//length是字符数组string的总容量
void replaceBlank(char string[], int length)
{
	if (string == NULL && length <= 0)
		return;
	int originalLength = 0;//字符串的实际长度
	int numBlank = 0;//空格的个数
	int i = 0;
	while (string[i] != '\0')
	{
		originalLength++;
		if (string[i] == ' ')
			numBlank++;
		i++;
	}
	int newLength = originalLength + numBlank * 2;//把空格替换成人“%20”之后的长度
	if (newLength > length)
		return;

	int indexOfOriginal = originalLength;
	int indexOfNew = newLength;

	while (indexOfOriginal >= 0)
	{
		if (string[indexOfOriginal] == ' ')
		{
			string[indexOfNew--] = '0';//先赋值再减减
			string[indexOfNew--] = '2';
			string[indexOfNew] = '%';
		}
		else
		{
			string[indexOfNew] = string[indexOfOriginal];
		}
		indexOfNew--;
		indexOfOriginal--;
	}
}
int main()
{
	char string[20] = "we are happy.";
	replaceBlank(string, 20);
	cout << string << endl;
}

 

 

 

 上图展示的是新创建一个数组，本题的意思是将A2的数字全部添加在 A1上，即最后合并的数组还是A1，如果从前往后比较赋值的话，A1中后面的数字需要多次往后移动。所以可以借助上面替换空格的思想，从后往前比较赋值：

#include<iostream>
using namespace std;

void combineArray(int A[], int B[],int numA,int numB)
{
	int sumLength = numA + numB -1;
	numA--;numB--;
	while (1)
	{
		if (numA < 0)
		{
			while (numB >= 0)
			{
				A[sumLength] = B[numB];
				numB--; sumLength--;
			}
			break;
		}
		if (numB < 0)
		{
			while (numA >= 0)
			{
				A[sumLength] = A[numA];
				numA--; sumLength--;
			}
			break;
		}
		if (A[numA] >= B[numB])
		{
			A[sumLength] = A[numA];
			numA--;sumLength--;
		}
		else
		{
			A[sumLength] = B[numB];
			numB--;sumLength--;		
		}	
	}
}