老实说,貌似直接可以实现。。代码如下:
class Solution
{
public string replaceSpace(string str)
{
return str.Replace(" ","%20");
}
}
使用两个指针,方法借鉴于Edison Chou。
先遍历一次字符串,这样就能统计出字符串中空格的总数,并可以由此计算出替换之后的字符串的总长度。
以前面的字符串"We arehappy."为例,"We are happy."这个字符串的长度是14(包括结尾符号'\0'),里面有两个空格,因此替换之后字符串的长度是18。从字符串的后面开始复制和替换。准备两个指针,P1和P2。P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。接下来向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。接着向前复制,直到碰到第二、三或第n个空格。时间复杂度为O(n),实现方法如下图:
代码实现:
public static void ReplaceBlank(char[] target, int maxLength)
{
if (target == null || maxLength <= 0)
{
return;
}
// originalLength 为字符串target的实际长度
int originalLength = 0;
int blankCount = 0;
int i = 0;
while (target[i] != '\0')
{
originalLength++;
// 计算空格数量
if (target[i] == ' ')
{
blankCount++;
}
i++;
}
// newLength 为把空格替换成'%20'之后的长度
int newLength = originalLength + 2 * blankCount;
if (newLength > maxLength)
{
return;
}
// 设置两个指针,一个指向原始字符串的末尾,另一个指向替换之后的字符串的末尾
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while (indexOfOriginal >= 0 && indexOfNew >= 0)
{
if (target[indexOfOriginal] == ' ')
{
target[indexOfNew--] = '0';
target[indexOfNew--] = '2';
target[indexOfNew--] = '%';
}
else
{
target[indexOfNew--] = target[indexOfOriginal];
}
indexOfOriginal--;
}
}