一 题目描述:剑指 Offer 05. 替换空格 - 力扣(LeetCode) (leetcode-cn.com)
请实现一个函数,把字符串 s 中的每个空格替换成" "。
示例 1:
输入:s = "We are happy."输出:"We are happy."
二 解题思路
题目本身要求很明确,并不难理解。思路也比较简单,先统计空格数量,对s进行扩容然后从后往前依次复制字符串。
先提供一版c 代码,如下:
class Solution {
public:
string replaceSpace(string s) {
//原书使用的是数组,但是这里使用的是字符串。因此需要注意到两点不同:
//1、s的末尾不是‘\0’
//2、计算空格的方法要发生改变,而且增加空格的时候必须要对s的长度进行调整,而不能像数组那样,直接移动指针。
int orginalLength = s.size() - 1;
int numberOfBlank =0;
for (auto c : s){
if (c == ' ') numberOfBlank;
}
int newLength = orginalLength numberOfBlank * 2;
s = string(numberOfBlank * 2,' ');
int indexOriginal = orginalLength;
int indexNew = newLength;
while(indexOriginal >= 0 && indexNew > indexOriginal){//注意这里indexNew > indexOriginal即可,因为等于之后说明前面字符没有空格了完全一致了
if (s[indexOriginal] == ' '){
s[indexNew--] = '0';
s[indexNew--] = '2';
s[indexNew--] = '%';
}
else{
s[indexNew--] = s[indexOriginal];
}
--indexOriginal;
}
return s;
}
};
三 其他版本代码提交出错了
刷题时有时会用不同语言写代码,比如c。这里使用相同思路改成c代码时提交就出错了。
在对字符数组扩容时,可以使用realloc和malloc两种方式,当然这里更推荐使用relloc。
下面是对两种方式代码写法需要注意的地方做个比较。
版本一代码使用malloc开辟新的空间,需注意如下代码:
char* replaceSpace(char* s){
if (s == NULL)
return NULL;
int originalLength = 0;
int numOfBlack = 0;
int i = 0;
while (s[i] != '\0')
{
originalLength;
if (s[i] == ' ')
numOfBlack;
i;
}
if(numOfBlack==0)
return s;
int newLength = originalLength numOfBlack * 2;
printf("newLength is %d,originalLength is %d\n", newLength, originalLength);
int indexOforiginal = originalLength-1;
int indexOfNew = newLength-1;
void *p=malloc( sizeof(char) * (newLength 1));
char *result;
if (p != NULL)
{
result = (char*)p;
//memset(result, 0, newLength 1);
result[newLength] = '\0';
}
printf("the indexOforiginal char is %c\n", s[indexOforiginal-1]);
while (indexOforiginal >= 0 && indexOfNew >= indexOforiginal)//因为时重新开辟空间,这里一定要indexOfNew >= indexOforiginal,将字符全部复制,否则因为没赋值开头区域出现乱码
{
if (s[indexOforiginal] == ' ')
{
result[indexOfNew--] = '0';
result[indexOfNew--] = '2';
result[indexOfNew--] = '%';
}
else
result[indexOfNew--] = s[indexOforiginal];
--indexOforiginal;
}
return result;
}
但是如果是使用realloc时,就不必所有字符全部复制了,代码如下:
char* replaceSpace(char* s){
if (s == NULL)
return NULL;
int originalLength = 0;
int numOfBlack = 0;
int i = 0;
while (s[i] != '\0')
{
originalLength;
if (s[i] == ' ')
numOfBlack;
i;
}
if(numOfBlack==0)
return s;
int newLength = originalLength numOfBlack * 2;
printf("newLength is %d,originalLength is %d\n", newLength, originalLength);
int indexOforiginal = originalLength-1;
int indexOfNew = newLength-1;
void *p=realloc(s, sizeof(char) * (newLength 1));
if (p != NULL)
{
s = (char*)p;
s[newLength] = '\0';
}
//char* result = (char*)malloc(newLength 1);
//memset(result, 0, newLength 1);
//result[indexOfNew] = '\0';
printf("the indexOforiginal char is %c\n", s[indexOforiginal-1]);
while (indexOforiginal >= 0 && indexOfNew >indexOforiginal)//注意这里不需要indexOfNew >=indexOforiginal,因为相等时旧的元素已经存在,不必多复制一次
{
if (s[indexOforiginal] == ' ')
{
s[indexOfNew--] = '0';
s[indexOfNew--] = '2';
s[indexOfNew--] = '%';
}
else
s[indexOfNew--] = s[indexOforiginal];
--indexOforiginal;
}
return s;
}
,