c++ - 从字符串中删除重复字符的函数仅部分适用于相邻字符

Question

我知道这是一个经常被问到的问题，如果它是愚蠢的，我深表歉意，但我正在尝试从文件中的字符串中删除重复的字符，并将新字符串放入另一个文件中。那部分进展顺利。

我遇到的主要问题是我的算法删除字符，它只适用于相同的连续字符，即使这样也只能部分删除。我正在尝试在 for 循环中使用 user.erase() 来执行此操作，但正如我所说，它不起作用。我哪里错了？

string removeRepeats(string strIn,string &strOut){
    int i;
    int len = strIn.length();
    for(i = 0;i < len; i++){
        if(strIn[i] == strIn[i+1]){
            strIn.erase(i+1,1);
        }
        len = strIn.length();
    }
    return strOut = strIn;
}

这些是来自示例文件的输入字符串中的字符串:

aaaaaabbccccc
nnnnmmmvvv
rocko 
refrigerate pool 
fungus 

这是程序运行后的结果:

aaabccc                                                                                                                                                 
nnmmvv                                                                                                                                                  
rocko                                                                                                                                                   
refrigerate                                                                                                                                             
pol                                                                                                                                                     
fungus  

Answer 1

您只检查相邻字符:if(strIn[i] == strIn[i+1]) { ...

你可以更有效地做到这一点，但我想先做一些评论:

返回或通过引用传递，但不能同时返回这两者

• 你返回strOut 和通过strOut引用。你应该选择一个或另一个。在我下面写的代码中，我选择返回strOut .

最小化变量的范围

• 与 C 不同，在 C++ 中，您可以在 for 中初始化变量-循环。您还需要尝试最小化除循环变量之外的其他变量的范围。在您的代码中，您创建了一个变量 len .如果您使用 for(size_t i = 0; i < strIn.length(); ++i)相反，您不需要在 if 之后更新它-声明。

返回一个作业很很奇怪

• return strOut = strIn;很奇怪。在 C++ 中您不会经常看到这种情况(请参阅返回或按引用传递，但不能两者都)。如果你真的想return strOut , 创建 strIn 的拷贝更有意义在你改变它之前，在拷贝上做你所有的字符串突变。

以下是我对您的代码所做的更改(无论算法的正确性如何):

std::string removeRepeats(std::string strIn){
    std::string strOut = strIn;
    for(size_t i = 0;i < strOut.length(); ++i){
        if(strOut[i] == strOut[i+1]){
            strOut.erase(i+1,1);
        }
    }
    
    return strOut; 
}

你会发现这更干净。

现在解决您的问题。

由于只有 128 个 ASCII 字符，您可以创建一个 bool 数组并检查您之前是否见过某个字符。

因为您想保留重复字符的最后一个，所以我们需要有点技巧。下面的代码将保留重复字符的第一个。

C++11 批准

std::string remove_repeats(std::string input_string) {
  // You have seen no characters yet
  bool seen[128] = { false }; 
  
  std::string output_string = "";

  // for every character in the string
  for(auto c: input_string) {
    // if we haven't seen the the ASCII yet
    if(!seen[128-c]) {
      // append it to our output string
      output_string+=c;
      // mark the letter as seen
      seen[128-c] = true;
    }
  }
   
  return output_string;
}

这是 ideone .

如果你不会使用 C++11，你可以这样做:

std::string remove_repeats(std::string input_string) {
  // You have seen no characters yet
  bool seen[128] = { false };  
  
  std::string output_string = "";

  // for every character in the string
  for(size_t i = 0; i < input_string.length(); ++i) {
    char c = input_string[i];
    // if we haven't seen the the ASCII yet
    if(!seen[128-c]) {
      // append it to our output string
      output_string+=c;
      // mark the letter as seen
      seen[128-c] = true;
    }
  }
   
  return output_string;
}

这是 ideone对于非 C++11 版本。

然而

您想保留最后一个。这就是它变得有趣的地方。

如果我们反转字符串 (1)，运行我们的算法 (2)，然后重新反转 (3)，我们将获得所需的输出:

(1) "hello world" -> "dlrow olleh"

(2) "dlrow olleh" -> "dlrow eh"

(3) "dlrow eh" -> "he world"

方法如下:

std::string remove_repeats(std::string input_string) {
  // You have seen no characters yet
  bool seen[128] = { false };  

  // Reverse the input string
  std::reverse(input_string.begin(), input_string.end());
  
  std::string output_string = "";

  // for every character in the string
  for(auto c: input_string) {
    // if we haven't seen the the ASCII yet
    if(!seen[128-c]) {
      // append it to our output string
      output_string+=c;
      // mark the letter as seen
      seen[128-c] = true;
    }
  }

  // Reverse the output string
  std::reverse(output_string.begin(), output_string.end());

  return output_string;
}

一定要#include <algorithm>对于 std::reverse .

最后的工作 ideone