题目
笔者比较笨，所以会写的很详细，方便自己后序复盘和分享给别人！希望大佬们不要嫌弃我的事多~哈哈哈！感谢大佬们支持！
题目链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
思路
- 根据规律可知，替换之后的长度 = 原来替换前的长度 +空格个数*2 (不包括\0) ->所以替换后末尾要手动放\0，或者替换过程把\0也放过去
- 所以：第一步：遍历字符串，求出空格个数
- 求出替换之后的长度记为：newlength 原来的长度记为:length
- 进行填充，从后往前填充，用两个变量来控制, i 下标范围：[0,length] ->这种情况包含了\0，要把\0也替换过去 而若下标范围为：[0,length) ->这种情况是没有把\0也替换过去，所以最后要在newlength位置手动放\0
- pos取值范围：[0,newlength] /[0,newlength)
- 如果i指向的字符不是空格，就把此时的字符放到pos位置，pos–,i–
- 如果是空格就放%20到pos位置，pos–三次，i–一次
手动最后位置放\0
方法1：从后往前替换
写法1：下标范围为：**[0，newlength) **和 [0,newlength) 最后拷贝完手动放\0
#include<stdio.h> #include<string.h> void ReplaceSpace(char* str, int length) { //1.计算空格的个数 int i = 0; int spcount = 0; for (i = 0; i < length; i++) { if (str[i] == ' ') spcount++; } //2.计算替换空格后新的长度和最后的位置 int newlengh = length + spcount * 2; int pos = newlengh - 1; //3.从后往前填充 for (i = length - 1; i >= 0; i--) { //空格 if (str[i] == ' ') { str[pos--] = '0'; str[pos--] = '2'; str[pos--] = '%'; } //非空格 else { str[pos--] = str[i]; } } //最后手动在newlength位置放\0 str[newlengh] = '\0'; } int main() { char arr[20] = " We Are Happy"; ReplaceSpace(arr, strlen(arr)); printf("%s\n", arr); return 0; }
写法2：下标范围为：[0，newlength] 和 [0,newlength] 直接把\0也后移
void ReplaceSpace(char* str, int length) { assert(str); //统计空格的个数 int count = 0; for (int i = 0; i < length; i++) { if (str[i] == ' ') { count++; } } //计算替换后的长度 = 原来长度+空格个数*2 int newlength = length + count * 2; int pos = newlength; //替换 -从后往前覆盖 //如果不是空格就把pos位置的字符放到pos位置 //如果是空格就在pos位置往前放%20 // \0也要替换，所以长度为:[0,length] //从后往前存放 for (int i = length; i >= 0; i--) { if (str[i] == ' ') { //如果是空格就在pos位置往前放 %20 str[pos--] = '0'; str[pos--] = '2'; str[pos--] = '%'; } else { str[pos--] = str[i]; } } } int main() { char arr[50] = " WeAreHappy"; ReplaceSpace(arr, strlen(arr)); printf("%s\n", arr); return 0; }
方法2：开辟新空间
思路：
- 第一步：遍历字符串，求出空格个数为count
- 求出替换之后的长度记为：newlength 原来的长度记为:length，
newlength = length + count*2求出字符串的长度是不包含\0的！！ - 开辟一个大小为newlength+1大小的数组arr （多加一个空间是为了存放\0
- 分别使用变量控制下标 i 控制str数组 j控制arr数组
如果i指向的不是空格，就把i指向的内容放到arr数组的j位置,i++,j++
如果是i指向的是空格，就在arr数组后面覆盖%20，j++三次，然后i++跳过空格，
不管怎样i都要++ - 最后把arr数组的内容拷贝回去，然后释放掉arr
#include<stdlib.h> //开辟新空间 void ReplaceSpace(char* str, int length) { //统计空格个数 int count = 0; int i = 0; for (i = 0; i < length; i++) { if (str[i] == ' ') { count++; } } int newlength = length + count * 2; //计算出的长度不包括\0 char* arr = (char*)malloc(sizeof(char) * (newlength+1));//要存放\0,所以要多开辟一个空间 if (arr == NULL) { printf("malloc fail\n"); exit(-1); } //分别使用变量控制下标 i 控制str数组 j控制arr数组 //如果i指向的不是空格，就放到arr数组的j位置,i++,j++ //如果是i指向的是空格，就在arr数组中替换为%20，i++一次，j++三次 //不管怎样i都要++ int j = 0; for (i = 0; i < length; i++) { //i指向的是空格 if (str[i] == ' ') { arr[j++] = '%'; arr[j++] = '2'; arr[j++] = '0'; } else { arr[j++] = str[i]; } } //在newlength位置放\0 arr[newlength] = '\0'; //拷贝回去，把\0也拷贝过去，所以范围为：[0，newlength] for (j = 0; j <=newlength; j++) { str[j] = arr[j]; } //最后要释放空间 free(arr); arr = NULL; } int main() { char arr[50] = "WeAre Happy"; ReplaceSpace(arr, strlen(arr)); printf("%s\n", arr); return 0; }
代码
char* replaceSpace(char* s){ /* int i = 0; int len = strlen(s); int count = 0; //统计空格个数 for(i = 0;i<len;i++) { if(s[i] == ' ') { count++; } } //开辟新空间 int newlength = count*2+len; char* str = (char*)malloc(sizeof(char)*(newlength+1)); //多开辟一个空间存放\0 int j = 0; for(i = 0;i<len;i++) { if(s[i] == ' ') { str[j++] = '%'; str[j++] = '2'; str[j++] = '0'; } else { str[j++] = s[i]; } } str[j] = '\0'; //或者str[newlength] = '\0' 在最后位置放\0 return str; */ //法2：原地扩容 int i = 0; int len = strlen(s); int count = 0; //统计空格个数 for(i = 0;i<len;i++) { if(s[i] == ' ') { count++; } } //开辟新空间 int newlength = count*2+len; s = (char*)realloc(s,sizeof(char)*(newlength+1)); //多开辟一个空间存放\0 //从后往前 int pos = newlength; s[pos] = '\0'; for(i = len ;i> 0;i--) { if(s[i] == ' ') { s[pos--] = '0'; s[pos--] = '2'; s[pos--] = '%'; } else{ s[pos--] = s[i]; } } return s; }
