我明天有一个编程面试,我正在为此练习。我读到一个常见的问题是使用原型(prototype)找到字符串中的第一个重复字符
size_t FindFirstRepeatedChar ( char * );
我能想到的最好的解决方案是
#include <string.h>
#include <vector>
char FindFirstRepeatedChar ( char * S )
{
/* Returns the index of the first repeated character in the string S.
Assume S does indeed contain a repeat.
*/
std::vector<bool> booVec(128,false)
for (char * c1(S), * c2(S+strlen(S)); c1 != c2; ++c1)
{
size_t i((size_t)*c1);
if (booVec[i] == false) booVec[i] = true;
else return (char)i;
}
}
但我想知道
(1) 这是错的吗?
(2) 如果没有错,有什么方法可以节省电子,即进一步优化吗?
(3) 是否有一个标准库算法,我可以利用它在 1 行中解决它?
最佳答案
通常面试并不期望你说这个库已经做到了,因为他们想检查你是否可以编码和编写算法。
至于改进它,我会在一次采访中说他们可能不是在要求最好的优化,而是更多的是为了一些易于阅读的东西(这也意味着在你写它时出错的风险较小)。
我可能会在第一个循环中编写一个非常简单的嵌套循环。它速度较慢但非常容易编写。如果他们让我做的更快,我会稍后转向您的解决方案。
你在那个程序中遇到的主要错误是你输入了一个 char
(通常是 8 位),而你的 vector 只存储了 128 个元素,所以如果其中有非 ASCII 字符,它就会崩溃字符串。
关于c++ - 针对 "Find the first repeated character in a string"挑战的最紧凑、高效、可读和聪明的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29788084/