您好,登錄后才能下訂單哦!
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù),將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如,當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
*注:設(shè)給定字符串長(zhǎng)度為n。語(yǔ)言:C++
解法1:正向遍歷,遇到空格即進(jìn)行替換,并將其后的元素相應(yīng)后移。
void replaceSpace(char *str,int length) {
if(length <= 0)
return;
char rep[] = "%20";
char *out;
int cnt = 0;
for(int i = 0; i < length; ++i)
{
if(str[i] == ' ')
{
for(int j = length+1; j > i; --j)
str[j] = str[j-2];
length += 2;
strncpy(str+i, rep, 3);
}
}
}
時(shí)間復(fù)雜度:O(n^2),空間復(fù)雜度:O(1)
解法2:正向遍歷計(jì)算空格數(shù),再反向遍歷進(jìn)行空格替換。
void replaceSpace(char *str,int length) {
if(length <= 0)
return;
int cnt = 0;
for(int i = 0; i < length; ++i)
{
if(str[i] == ' ')
cnt += 2;
}
for(int i = length - 1; i >= 0; --i)
{
if(str[i] != ' ')
str[i + cnt] = str[i];
else
{
cnt -= 2;
str[i + cnt] = '%';
str[i + cnt + 1] = '2';
str[i + cnt + 2] = '0';
}
}
}
時(shí)間復(fù)雜度:O(n),空間復(fù)雜度:O(1)
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。