從矢量中提取一定數量的數字

我在試圖找到一種方法從一系列數字中提取符合條件的最長序列：每個數字必須是其後面數字的前綴。從矢量中提取一定數量的數字

例如：對於系列：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

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

從矢量中提取一定數量的數字

回答

相關問題