博客


一、题目描述


实现函数，把字符串中的空格替换为”%20″

例如：把字符串”We are like study.“中的空格全都替换为”%20″,替换之后字符串就变为了”We%20are%20like%20study.”


二、题目的由来




1.原因

在网络编程中,如果URL中有含有特殊字符，如空格、’#’等，可能就会导致服务器无法获得正确的参数值，所以需要我们把这些特殊字符进行替换，替换为服务器可以进行识别的字符

2.替换规则

把需要替换的字符改为：%xx，xx为要进行替换的字符的ASCII码的16进制表示，例如空格的ASCII码为32，用16进制表示的话为20，所以空格就被替换为”%20″，字符’#‘的ASCII码为25，用16进制表示的话为23，那字符’#’就会被替换为”%23″


三、代码实现




1.思路

在替换空格时，从后向前开始进行搬移，因为把一个字符替换为了3个字符，所以数组的长度会变长，替换后数组的长度=空格的数量*2+替换之前数组的长度

给两个标记，p1标记原数组（替换之前的数组）的最后一个元素，p2标记新数组（替换之后的数组）的最后一个元素，在p1没有遇到空格之前，把p1标记的元素搬移到p2标记的位置，搬移之后，p1和p2都向前移动，当p1遇到空格后，p1向前移动一步，把p2标记的位置依次写入”%20″，在写的过程中，每写一个字符，p2向前移动一步，循环这个过程，直到把所有空格替换完成

2.源代码

#include<stdio.h>
#include<stdlib.h>
//size为数组的容量
void Replace(char arr[], int size)
{
 if (arr == NULL || size < 0)
  return;
 int i = 0;
 int numBlank = 0;
 int originalLength = 0;//数组的实际长度
 int newLength = 0;//空格被替换后，数组的长度
 int indexOriginal = 0;//初始值为原数组的最后一个元素
 int indexNew = 0;//初始值为空格被替换后，数组的最后一个元素
 //1.遍历数组，计算数组的实际长度和数组中的空格数量
 while (arr[i] != '\0')
 {
  ++originalLength;
  if (arr[i] == ' ')
   ++numBlank;
  ++i;
 }
 //2.替换空格
 newLength = originalLength + numBlank * 2;
 if (newLength < originalLength)
  return;
 indexNew = newLength;
 indexOriginal = originalLength;
 while (indexOriginal >= 0 && indexNew>indexOriginal)
 {
  if (arr[indexOriginal] == ' ')
  {
   arr[indexNew--] = '0';
   arr[indexNew--] = '2';
   arr[indexNew--] = '%';
  }
  else
  {
   arr[indexNew--] = arr[indexOriginal];
  }
  indexOriginal--;
 }
}
int main()
{
 char arr[30] = "we are like study";
 //char arr[30] = "wearelikestudy";
 //char arr[30] = "we ";
 //char arr[30] = "    we are";
 //char arr[30] = " ";
 int size = sizeof(arr) / sizeof(arr[0]);
 int i = 0;
 Replace(arr, size);
 for (; i < size; ++i)
 {
  printf("%c", arr[i]);
 }
 printf("\n");
 system("pause");
 return 0;
}

运行结果：


四、时间复杂度


在整个替换的过程中，每个字符只会被搬移一次

时间复杂度为O(N)


五、本题的考察点


1.对内存覆盖的警惕（由于是把一个字符替换为3个字符，那替换的时候，就会涉及到内存覆盖）

2.逆向思维

对于这种题，大家一般第一反应都是从前往后进行替换，这种替换方式也可以完成题目的要求，但是时间复杂度会比较高，高达O(N^2)，假如有N个空格，那有些字符可能在整个替换过程中，被搬移N次，所以时间复杂度为N*N

此时，如果想到从后往前进行搬移的话，那就会提高效率

3.在编程的过程中，一定要注意时间复杂度的问题