通過(guò)我在網(wǎng)上找到的一些編程面試挑戰(zhàn)，我不得不編寫(xiě)一個(gè)算法來(lái)反轉(zhuǎn) const char * 并返回一個(gè)指向新 char * 的指針。我想我有它，但為了讓它正常工作，我不得不做一些奇怪的事情——基本上必須自己考慮空終止字符。不知何故，我覺(jué)得這是錯(cuò)誤的，但我很難過(guò)，我想知道是否有人可以幫助我：
char*reverse(constchar* str)
{
intlength =strlen(str);
char* reversed_string =newchar[length+1];
for(inti =0; i < length; ++i)
? {
reversed_string[i] = str[(length-1) - i];
? }
//need to null terminate the string
reversed_string[length] ='\0';
returnreversed_string;
}
intmain(intargc,char* argv[])
{
char* rev_str =reverse("Testing");
cout <<"Your string reversed is this: "<< rev_str << endl;
deleterev_str;
rev_str =0;
return0;
}
上面的 for 循環(huán)有錯(cuò)字。檢查循環(huán)變量 i 應(yīng)該是 <= 而不是 <，否則對(duì)于奇數(shù)個(gè)元素將失敗。for(int i = 0; i <= 長(zhǎng)度/2; ++i)
char*reverse(constchar* str)
{
if(!str)
returnNULL;
intlength =strlen(str);
char* reversed_string =newchar[length+1];
for(inti =0; i < length/2; ++i)
? {
reversed_string[i] = str[(length-1) - i];
reversed_string[(length-1) - i] = str[i];
? }
//need to null terminate the string
reversed_string[length] ='\0';
returnreversed_string;
}
一半的時(shí)間，但復(fù)雜性相同（注意可能會(huì)因一個(gè)錯(cuò)誤而關(guān)閉）
如果傳遞了一個(gè)空指針，那么到目前為止提交的所有strlen()答案都將失敗——它們中的大多數(shù)會(huì)跳轉(zhuǎn)到立即調(diào)用一個(gè)可能的空指針——這可能會(huì)導(dǎo)致你的進(jìn)程出現(xiàn)段錯(cuò)誤。
許多答案都對(duì)性能著迷，以至于他們錯(cuò)過(guò)了問(wèn)題的關(guān)鍵問(wèn)題之一： reverse aconst char *，即您需要制作反向副本，而不是就地反向。如果需要副本，您會(huì)發(fā)現(xiàn)很難將迭代次數(shù)減半！
不需要臨時(shí)變量的方法
intlength = strlen(string);
for(inti =0; i < length/2; i++) {
string[i] ^=string[length - i] ^=string[i] ^=string[length - i];
}
字符串反轉(zhuǎn)到位，沒(méi)有臨時(shí)變量。
staticinlinevoid
byteswap(char*a,char*b)
{
? *a = *a^*b;
? *b = *a^*b;
? *a = *a^*b;
}
void
reverse(char*string)
{
char*end =string+ strlen(string) -1;
while(string< end) {
byteswap(string++, end--);
? }
}
它不會(huì)更有效，但是您可以通過(guò)將每個(gè)字母推入堆棧，然后將它們彈出到新分配的緩沖區(qū)中來(lái)展示數(shù)據(jù)結(jié)構(gòu)的知識(shí)。
這將需要兩次通過(guò)和一個(gè)臨時(shí)堆棧，但我可能會(huì)更相信自己第一次就能做到這一點(diǎn)，然后不會(huì)像上面那樣犯一個(gè)錯(cuò)誤。
char*stringReverse(constchar* sInput)
{
std::size_tnLen =strlen(sInput);
std::stack charStack;
for(std::size_ti =0; i < nLen; ++i)
? ? {
charStack.push(sInput[i]);
? ? }
char* result =newchar[nLen +1];
std::size_tcounter =0;
while(!charStack.empty())
? ? {
result[counter++] = charStack.top();
charStack.pop();
? ? }
result[counter] ='\0';
returnresult;
}
