c++ - 针对 "Find the first repeated character in a string"挑战的最紧凑、高效、可读和聪明的解决方案

Question

我明天有一个编程面试，我正在为此练习。我读到一个常见的问题是使用原型(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 行中解决它？

Answer 1

通常面试并不期望你说这个库已经做到了，因为他们想检查你是否可以编码和编写算法。

至于改进它，我会在一次采访中说他们可能不是在要求最好的优化，而是更多的是为了一些易于阅读的东西(这也意味着在你写它时出错的风险较小)。

我可能会在第一个循环中编写一个非常简单的嵌套循环。它速度较慢但非常容易编写。如果他们让我做的更快，我会稍后转向您的解决方案。

你在那个程序中遇到的主要错误是你输入了一个 char(通常是 8 位)，而你的 vector 只存储了 128 个元素，所以如果其中有非 ASCII 字符，它就会崩溃字符串。