从矢量中提取一定数量的数字

我在试图找到一种方法从一系列数字中提取符合条件的最长序列：每个数字必须是其后面数字的前缀。从矢量中提取一定数量的数字

例如：对于系列：523,742,7421,12,123,1234,87它应该显示12,123,1234。

我想过把这个序列存储在一个向量中，然后迭代它，并移动满足另一个向量条件的数字。不过，我被困在选择（在上面的例子中12,123,1234代替742, 7421）的最长序列。这里是我写到目前为止代码：

 bool prefix(int a, int b){ 
      if ((b/10 - ((b % 10))/10) == a) 
      return 1; 
      else return 0; 
      } 

     vector<int> choose_sequence(vector<int> &series){ 
      vector<int> right_sequence; 
      int count = 0; 
       for (int i = 0; i < series.size();){ 
       for (int j = i + 1; j < series.size();){ 
        if (prefix(series.at(i), series.at(j))){ 
        right_sequence.push_back(series.at(i)); 
        right_sequence.push_back(series.at(j)); 
         i=j; 
         j++; 

        } 
       else 
       i++; 
      } 
       } 
      return right_sequence; 
     }

任何建议或修正的欢迎和最appreciate.Also，如果你知道使用另一种数据类型比载体更好的方法，请分享。

来源

2014-03-25 Georgiana.b

这是一个典型的动态规划问题。你有没有考虑过使用它？ –

我认为解决这个问题的经典方法是创建第二个向量，该向量将为每个位置包含在该位置结束的序列的长度以及序列中前一个元素的位置（-1如果没有以前的元素）。对于您的示例，向量将如下所示： count：1,1,1,2,3,1, prev：-1，-1,1，-1，3，4，-1

您将从计数中选择最大值并使用prev确定序列。

因此，我们的最大是3，位置5和相应的元素为1234 先前元件是在位置4中的原始矢量和的值是123 先前元件是在3位和值是12. 上一个元素位于-1，这意味着没有以前的元素，所以我们有我们的序列：12,123,1234。

另一种方法是尝试设置开始序列的长度在某个位置和下一个元素的位置。您将有： count：1，2，1，3，2，1，1 下一个：-1，2，-1，4，5，-1，-1

我们的最大值是3，但现在我们有序列的第一个元素（位置3，值12）。下一个元素位于位置4（值为123）。下一个元素位于位置5（值为1234）。下一个元素位于-1，这意味着我们到达了序列的末尾。

该方法的优点是序列以“正确”顺序生成。

来源

2014-03-25 18:15:46 skortzy

这很有道理。谢谢！ –

您可以在没有任何额外内存的情况下执行此操作，并且只能对输入向量进行一次遍历。

std::vector<int> longestSequence(const std::vector<int>& numbers) 
{ 
    std::vector<int> result; 
    if (numbers.empty()) 
     return result; 
    size_t longestStart = 0, longestLength = 0; 
    size_t start = 0; 
    for (size_t i = 1, imax = numbers.size(); i < imax; ++i) { 
     if (numbers[i]/10 != numbers[i - 1]) { 
      if (i - start > longestLength) { 
       longestStart = start; 
       longestLength = i - start; 
      } 
      start = i; 
     } 
    } 
    if (numbers.size() - start > longestLength) { 
     longestStart = start; 
     longestLength = numbers.size() - start; 
    } 
    result.assign(begin(numbers) + longestStart, begin(numbers) + longestStart + longestLength); 
    return result; 
}

link to Ideone

来源

2014-03-25 20:44:10 alexeibs

非常优雅和巧妙。我的感激之情！ –

从矢量中提取一定数量的数字

回答

相关问题