c++ - 从 vector 中提取特定的数字序列

Question

我正在尝试找到一种方法来从一系列数字中提取满足条件的最长序列:每个数字必须是其后数字的前缀。

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

我想到了将序列存储在一个 vector 中，然后对其进行迭代并将满足条件的数字移动到另一个 vector 中。然而，我在选择最长的序列时遇到了困难(在上面的例子中是 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;
       }

欢迎并非常感谢任何建议或更正。此外，如果您知道使用其他数据类型而不是 vector 来执行此操作的更好方法，请分享。

Answer 1

我认为解决这个问题的经典方法是创建第二个 vector ，对于每个位置，该 vector 将包含在该位置结束的序列的长度和序列中前一个元素的位置(-1 如果没有前一个元素)。对于您的示例， vector 将类似于:计数:1、1、2、1、2、3、1上一页: -1, -1, 1, -1, 3, 4, -1

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

所以，我们的最大值是3，位置是5，对应的元素是1234。前一个元素在原始 vector 中的位置为 4，值为 123。前一个元素在位置3，值为12。前一个元素位于位置 -1，这意味着没有前一个元素，所以我们有序列:12、123、1234。

另一种方法是尝试设置从某个位置开始的序列的长度和下一个元素的位置。你将会拥有:计数:1、2、1、3、2、1、1下一个:-1、2、-1、4、5、-1、-1

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

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