请实现一个函数,把字符串中的每个空格替换成”%20”。例如输入“We are happy.”, 则输出”We%20are%20happy.”。
在网络编程中,如果URL参数中含有特殊字符,如空格、'#'等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成"%20"。再比如'#'的ASCII码为35,即十六进制的0x23,它在URL中被替换为"%23"。

思路一:从左向右扫描字符串替换

一个字符替换为三个
每遇到一个空格,空格后面所有字符向右移动两个位置
字符串长度为n, 对每个空格而言,需要移动后面O(n)个字符
算法的时间复杂度为O(n^2)

思路二:从右到左扫描字符串替换
统计空格数,字符串长度增加 空格数 * 2
维持两个指针p1, p2
p1指向原字符串长度末尾, p2指向新字符串长度末尾
当p1遇到空格时, p2 向前移动并替换字符为 '0' '2' '%'
把p1指针指向的字符拷贝到p2指针指向的字符
所有字符都只移动一次,时间复杂度为O(n)
下面的C实现是思路二的实现代码:

//
//  main.c
//  func
//
//  Created by 52coder on 2017/12/18.
//  Copyright © 2017年 52coder. All rights reserved.
//
#include <stdio.h>
#include <string.h>

void trimspace(char str[],int len)
{
    int i = 0;
    //空格个数
    int space = 0;
    //替换前字符串长度
    int real = 0;
    //新长度
    int newlen = 0;
    
    while(str[i] != '\0')
    {
        real += 1;
        if(' ' == str[i])
        {
            space += 1;
        }
        i++;
    }
    //计算实际长度,每个空格多出两个长度
    newlen = real + space * 2;
    if(newlen > len)
    {
        printf("Not enough space.newlen = %d,len = %d\n",newlen,len);
        return ;
    }
    int src = real;
    int dst = newlen;
    while(src >=0)
    {
        if (' ' == str[src])
        {
            str[dst--]='0';
            str[dst--]='2';
            str[dst--]='%';
        }
        else
        {
            str[dst--] = str[src];
        }
        --src;
    }
}
int main(int argc, const char * argv[])
{
    //测试用例
    char str[100] = "We are happy.";
    trimspace(str,sizeof(str));
    printf("%s\n",str);
    
    //测试用例
    char s[100] = "We are happy ,are you ojbk?";
    trimspace(s,sizeof(s));
    printf("%s\n",s);
    
    //测试用例
    char a[100] = "We are happy ,are you ojbk    ?    ";
    trimspace(a,sizeof(a));
    printf("%s\n",a);
    
    //测试用例
    char b[16] = "We are happy.";
    trimspace(b,sizeof(b));
    printf("%s\n",b);
    
    return 0;
}