0

我正在编写一个 C++ 程序，它将查找并打印整数向量的第一个最长的升序或降序连续子序列。例如，给定一个向量

 4, 2, 1, 2, 3, 4, 3, 5, 1, 2, 4, 6, 5

返回 1,2,3,4

我的代码如下：

但是，我不知道如何返回第一个最优解。例如，上面的序列有 1、2、4、6，也是 4 长。但是，我们只需要返回 1,2,3,4。

bool findLong(const vector<int> v)
{
  if (v.size() <1)
    return false;
  if (v.size() == 1){
    cout << v[0] << endl;
    return true;
  }
  vector::const_iterator itr_left, itr_right;
  itr_left = v.begin();
  itr_right = v.begin()+1;
  bool ascending_flag ;
  int counter =0;
  if (*itr_right > *(itr_right-1)){
    bool ascending_flag = true;
    ++ascending_counter;    
  } 
  else{
    bool ascending_flag = false;
    ++descending_counter;
  }
  int longest = INT_MIN;
  Vector<int>::iterator longest_left = v.begin(), longest_right =v.begin(); 
  ++itr_right; 
  while (itr_right != v.end())
  {
   if (ascending_flag && *itr_right > *(itr_right-1))
     ++ascending_counter; 

   if (!ascending_flag&& *itr_right < *(itr_right-1))     
     ++descending_counter;       

   if  (ascending_flag&& *itr_right < *(itr_right-1))
   {
     if (ascending_counter > longest )
     {
        longest  = ascending_counter;
        longest_left = itr_left;
        longest_right = itr_right;
    }
    itr_left = itr_right;    
    ascending_counter = 0 ;  
    ascending_flag = false;
  }
  if  (ascending_flag && *itr_right > *(itr_right-1))
  {
    if (descending_counter > longest )
    {
        longest  = descending_counter;
        longest_left = itr_left;
        longest_right = itr_right;
    }       
    itr_left = itr_right;      
    descending_counter = 0 ;
    ascending_flag = true;
  }
  ++itr_right;
 }
 for_each( longest_left , longest_right, print);
 cout << endl;
}

Void print(int i)
{
  cout << i << " , " ;
}

欢迎任何意见！

谢谢 ！

4

3 回答 3

1

您的代码中有很多错字：您隐藏了ascending_flag 的初始化您的长度计数似乎不正确。

以下应该有效（只要没有两个具有相同值的邻居）。

bool findLong(const vector<int>& v)
{
    if (v.empty())
        return false;
    if (v.size() == 1) {
        cout << v[0] << endl;
        return true;
    }
    vector<int>::const_iterator itr_left = v.begin();
    vector<int>::const_iterator itr_right = v.begin() + 1;
    vector<int>::const_iterator longest_left = itr_left;
    vector<int>::const_iterator longest_right = itr_right;
    bool ascending_flag = (*itr_right > *(itr_right - 1));

    for (++itr_right; itr_right != v.end(); ++itr_right)
    {
        if (ascending_flag ^ (*itr_right < *(itr_right - 1)))
        {
            if (itr_right - itr_left > longest_right - longest_left)
            {
                longest_left = itr_left;
                longest_right = itr_right;
            }
            itr_left = itr_right - 1;
            ascending_flag = !ascending_flag;
        }
    }
    for_each(longest_left, longest_right, print);
    cout << endl;
    return true;
}
于 2013-09-03T18:36:32.930 回答
1

以下是一些想法：

  1. 如果函数名为“findX()”，它应该返回 X（例如，指向序列第一个元素的指针或 NULL，或第一个元素的索引或 -1）。如果函数打印 X，它应该被命名为“printX()”。
  2. 目前尚不清楚您是否需要升序或严格升序（即 (1, 2, 2, 3) 是否适合您）。

  3. 你把事情复杂化了。如果您需要第一个序列，您只需使用反向迭代器并从头到尾，就像这样（我不使用迭代器，但应该清楚如何包含它们）：

    int maxLength=1, currentUp=1, currentDown=1; //Last element is sequence of 1 element
size_t result = v.length()-1;
for(size_t i = v.length()-1; i!=0; --i){
    if(v[i-1] > v[i]) {
        currentDown++; currentUp=0;
    } else if(v[i-1] < v[i]) {
        currentUp++; currentDown=0;
    } else {
        //Not clear what should happen, change may be needed
        currentUp++; currentDown++;
    }

    if(maxLength <= max(currentUp, currentDown)) {
        result = i-1;
        maxLength = max(currentUp, currentDown);
    }
}

return result;
于 2013-09-04T07:11:24.843 回答
0

好吧，对于初学者来说，您的函数将始终返回 true。

if (v.size() <1)
  return false;
if (v.size() == 1)
  cout << v[0] << endl;
return true;

应该是

if (v.size() <1) {
  return false;

} else if (v.size() == 1) {
  cout << v[0] << endl;
  return true;
}
于 2013-09-03T17:38:07.567 回答