您将如何改进这个算法? (c 字符串反转)
为了解决我在网上发现的一些编程面试挑战,我必须编写一个算法来反转 const char * 并返回指向新 char * 的指针。 我想我已经有了它,但为了让它正常工作,我必须做一些奇怪的事情 - 基本上必须自己解释空终止字符。 不知何故,我觉得这是错误的,但我很困惑,我想知道是否有人可以帮助我:
char * reverse(const char * str)
{
int length = strlen(str);
char * reversed_string = new char[length+1];
for(int i = 0; i < length; ++i)
{
reversed_string[i] = str[(length-1) - i];
}
//need to null terminate the string
reversed_string[length] = '\0';
return reversed_string;
}
int main(int argc, char * argv[])
{
char * rev_str = reverse("Testing");
cout << "Your string reversed is this: " << rev_str << endl;
delete rev_str;
rev_str = 0;
return 0;
}
Working through some programming interview challenges I found online, I had to write an algorithm to reverse a const char * and return a pointer to a new char *. I think I have it, but to make it work properly I had to do some wonky stuff - basically having to account for the null-terminating character myself. Somehow I feel this is wrong, but I'm stumped, and I was wondering if someone could help me out:
char * reverse(const char * str)
{
int length = strlen(str);
char * reversed_string = new char[length+1];
for(int i = 0; i < length; ++i)
{
reversed_string[i] = str[(length-1) - i];
}
//need to null terminate the string
reversed_string[length] = '\0';
return reversed_string;
}
int main(int argc, char * argv[])
{
char * rev_str = reverse("Testing");
cout << "Your string reversed is this: " << rev_str << endl;
delete rev_str;
rev_str = 0;
return 0;
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(20)
std::reverse
来自
适用于字符串和 char 数组:/EDIT:这当然会修改原始字符串。 但 STL 可以拯救你。 以下创建一个新的反转字符串。 不幸的是(?),如果不创建额外的(隐式)副本,这不能直接在 C
char
数组上工作:std::reverse
from<algorithm>
works for strings andchar
arrays:/EDIT: This, of course, modifies the original string. But STL to the rescue. The following creates a new reversed string. Unfortunately (?), this doesn't work directly on C
char
arrays without creating an additional (implicit) copy:我曾经有过这样的疑问。 这是我想到的第一个答案,但接下来的答案是,“现在就在不分配任何内存的情况下执行此操作。”
编辑:有些人对不使用指针表示不屑。 虽然这并不完全是最佳的,但可读性稍高一些。 其他人已经进入了指针解决方案,这里不再重复。
一位评论者质疑,如果没有(基于堆栈的)交换保持单元,它应该是可行的。 这样做的机制是按位异或。 将循环内部替换为
但一般来说,现代编译器可以优化朴素交换的局部变量。 有关详细信息,参见维基百科
I had this question once. That's the first answer that comes to mind, but the follow-up is, "now do it without allocating any memory."
EDIT: Some folks have expressed disdain for not using pointers. This is a tiny bit more readable, though not completely optimal. Others have entered the pointer solution, so I won't repeat it here.
One commenter challenged that it should be doable without a (stack based) holding cell for the swap. The mechanism for doing that is bitwise XOR. Replace the inside of the loop with
But in general, modern compilers can optimize out the local variable of a naive swap. For details, See Wikipedia
您的代码很简单并且不足为奇。 一些事情:
换句话说:
Your code is straight forward and unsurprising. A few things:
In other words:
呃? 没有人用高手指点一下吗?
希望多年的 Java 没有毁掉我的 C ;-)
编辑:用额外的 var 替换所有这些 strlen 调用。 strlen 最近返回什么? (感谢底座)。
Uh? No one did it with pointers?
Hopefully years of Java haven't ruined my C ;-)
Edit: replaced all those strlen calls with an extra var. What does strlen return these days? (Thanks plinth).
我知道这是非常不可移植的,但 x86 汇编器指令 bswap 允许您仅通过一条指令交换四个字节,这可能是增强代码的一个很好的途径。
这是如何让它与 GCC 一起工作的示例。
我的旧电脑上 Cygwin 下的结果:
I know this is highly unportable but x86 assembler instruction bswap lets you swap four bytes by means of just one instruction which can be a good path to boost the code.
This is an example of how to get it working with GCC.
The results on my old computer under Cygwin:
@Konrad Rudolph:(抱歉我没有“经验”来发表评论)
我想指出STL提供了一个reverse_copy() 算法,类似于 reverse() 。 您无需像以前那样引入临时变量,只需分配一个正确大小的新 char * 即可。
@Konrad Rudolph: (sorry I don't have the "experience" to post a comment)
I want to point out that the STL supplies a reverse_copy() algorithm, similar to reverse(). You need not introduce a temporary the way you did, just allocate a new char * of the right size.
你不能(不应该)这样做:
来自:http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example
You cannot (should not) do this:
From: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example
实际上,考虑到原始字符串不被修改的约束,我认为问题中给出的原始方法是最好的。 所有这些在人们发布的地方进行反转的奇特方法都很棒,但是一旦考虑到复制给定的字符串,它们都比简单地向后复制字符串效率低。
Actually, given the constraint that the original string be left unmodified, I think the original approach given in the question is the best. All these fancy approaches to reversing in place people are posting are great, but once copying the given string is factored in, they are all less efficient than simply copying the string backwards.
我们以前曾使用过这个问题,结果令人惊讶地发现很多人都做不到(即使有丰富的 C/C++ 经验!)。 我更喜欢就地变体,因为它节省了一些开销,并且只需要迭代 strlen(s)/2 个字符。
你在面试中的解决方案就很好。 使用指针而不是数组语法的(正确!)解决方案的评分会更高一些,因为它显示出对 C/C++ 编程中至关重要的指针的更高舒适度。
较小的批评是指出 strlen 返回 size_t 而不是 int,并且您应该在 rev_str 上使用 delete []。
We've used this question before -- with the surprisingly results of finding a lot of people that can't do it (even with significant C/C++ experience!). I prefer the in-place variant since it saves some overhead, and has the added twist of only needing to iterate over strlen(s)/2 characters.
Your solution in an interview would be fine. A (correct!) solution using pointer instead of array syntax would rate a bit higher since it shows a greater comfort level with pointers which are so critical in C/C++ programming.
The minor critiques would be to point out that strlen returns a size_t not an int, and you should use delete [] on rev_str.
WRT:“现在在没有临时保存变量的情况下执行此操作”...也许是这样的(并且暂时保留数组索引):
WRT: "Now do it without temporary holding variable"... Something like this perhaps (and keeping array indexing for now):
这很好用:
this works nicely:
我会像这样解决它(虽然我的c有点生锈,请原谅我)
I would have solved it sort of like this (my c is a bit rusty though, forgive me)
这不会更有效,但您可以通过执行诸如将每个字母推入堆栈,然后将它们弹出到新分配的缓冲区之类的操作来展示数据结构的知识。
这需要两次传递和一个临时堆栈,但我可能会更相信自己第一次就能正确完成此操作,然后不会犯像上面这样的错误。
It wouldn't be more efficient, but you could demonstrate knowledge of data structures by doing something like pushing each letter onto a stack, and then popping them off into your newly allocated buffer.
It would take two passes and a scratch stack, but I would probably trust myself more to get this right the first time then to not make an off-by one error like the above.
当作为面试官提出这个问题时,我正在寻找一个干净、易于理解的解决方案,并可能会问如何使最初的解决方案更加高效。 我对“智能”解决方案不感兴趣。
我在想这样的事情; 候选人是否在循环中因一个错误而导致旧的问题,他们是否预先分配了足够的内存,他们是否检查了错误的输入,他们是否使用了足够高效的类型。
不幸的是,正如已经指出的那样,太多人甚至无法做到这一点。
When asking this question as an interviewer, I am looking to a clean, understandable solution and may ask how the initial solution could be made more efficient. I'm not interested in 'smart' solutions.
I am thinking about thing like; has the candidate made the old with off by one error in their loop, do they pre-allocate enough memory, do they check to bad input, do they use sufficiently efficient types.
Unfortunately, as already pointed out, too many people can't even do this.
字符串就地反转,没有临时变量。
String reversed in place, no temp variable.
不需要临时变量的方法
A method that doesn't need temporary variables
如果我进行面试,我会对解决方案的质量更加挑剔,包括其稳健性,而不仅仅是性能。
如果传递空指针,到目前为止提交的所有答案都将失败 - 大多数答案都会立即在可能的空指针上调用
strlen()
- 这可能会导致你的段错误过程。许多答案都过于关注性能,以至于忽略了问题的关键问题之一:反转
const char *
,即您需要进行反转复制,不是原地反转。 如果需要副本,您会发现很难将迭代次数减半!这是一个面试问题,所以我们想了解算法的细节,但在现实世界中,这只是强调了尽可能使用标准库的价值。
If I was doing the interviewing I would be a bit more fussy with the quality of the solution in terms of its robustness, not just it's performance.
All of the answers submitted thus far will fail if passed a null pointer - most of them leap to immediately calling
strlen()
on a possible null pointer - which will probably segfault your process.Many of the answers are obsessive about performance to the point that they miss one of the key issues of the question: reverse a
const char *
, i.e. you need to make a reversed copy, not reverse in-place. You'll find it difficult to halve the number of iterations if a copy is required!This is an interview question, so we want to look at the details of the algorithm, but in the real world this just highlights the value of using standard libraries whenever possible.
。
时间减半,但复杂性相同(注意可能会因一个错误而偏离)
.
Half the time but same complexity (note may be off by one error)
上面的 for 循环有拼写错误。
循环变量 i 的检查应该是 <= 而不是 <,否则对于奇数个元素将会失败。
for(int i = 0; i <= 长度/2; ++i)
Above for loop has typo.
Check of loop variable i should be <= instead of <, othrewise will fail for odd no of elements.
for(int i = 0; i <= length/2; ++i)