3

对于 C++ 列表中的每次运行x或多个连续零，我想删除运行中除x它们之外的所有零。如果x = 0，则删除所有零。

我在想一个 C++ 函数，它接受一个列表，list<int> L和一个数字int x，作为输入。

例如，让L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8}.

  • 如果x = 0，则返回L = {7, 12, 2, 27, 10, 8}
  • 如果x = 1，则返回L = {7, 0, 12, 0, 2, 0, 27, 10, 0, 8}
  • 如果x = 2，则返回L = {7, 0, 12, 0, 0, 2, 0, 0, 27, 10, 0, 0, 8}
  • 如果x = 3，则返回L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 8}
  • 如果x = 4，则返回L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8}（与原始相同L）
  • 如果x >= 5，则返回原始L值，因为没有 5 个或更多连续零的运行。

几个月前，我使用 Python ( stackoverflow.com/questions/11732554/... ) 提出了上述相同的问题，并得到了很好的答案。现在我想用 C++ 完成这个任务。

任何帮助将不胜感激。

4

6 回答 6

5

这是一些应该完成这项工作的代码：

void DeleteAllZerosInARow(std::list<int>& theList, int x)
{
    if(x == 0)
    {
        theList.remove(0);
        return;
    }

    int streak = 0;
    std::list<int>::iterator itor = theList.begin();
    while(itor != theList.end())
    {
        if(*itor == 0)
            ++streak;
        else
            streak = 0;

        if(streak > x)
            itor = theList.erase(itor);
        else
            ++itor;
    }
}

基本上，您计算一行中有多少个零，如果是 则删除它们> x，否则继续迭代列表。

给出以下输出：

  • 0：7,12,2,27,10,8
  • 1：7,0,12,0,2,0,27,10,0,8
  • 2：7,0,12,0,0,2,0,0,27,10,0,0,8
  • 3：7,0,12,0,0,2,0,0,0,27,10,0,0,0,8
  • 4：7,0,12,0,0,2,0,0,0,27,10,0,0,0,0,8
  • 5：7,0,12,0,0,2,0,0,0,27,10,0,0,0,0,8

这取决于您的风格，remove_if可能是更C++友好的方式，但我发现直接操作值更清晰，并且不涉及新的数据类型（struct用于跟踪0您遇到的数量）。

代码无法使用的原因很简单，因为,和大数NTL::ZZ之间没有隐式转换，因此不能。你可以做的事情可能是这样的：int0NTL::ZZremove(0)

if(x == 0)
{
    static ZZ zero; // default value is 0, static so that it is only constructed once
    theList.remove(zero); // remove all items who are equal to "zero"
    return;
}
于 2013-01-15T19:08:22.830 回答
1

对于案例 0，您可以使用std::remove，对于案例 1，您可以使用std::unique仅适用于 的谓词0。对于更大的值，要么设计一个偷偷摸摸的有状态谓词来使用，unique要么借用它的逻辑来应用于更大的序列。

于 2013-01-15T19:03:04.947 回答
1

最简单的方法是返回 astd::vector<int>并使用push_back，这样您就不必担心分配正确大小的数组。

template<typename Iter>
std::vector<int> filter_zeroes(Iter start, Iter end, const size_t num_zeroes)
{
    std::vector<int> output;
    size_t zero_count = 0;
    while (start != end)
    {
        if (*start != 0)
        {
            output.push_back(*start);
            zero_count = 0;
        }
        else if (zero_count < num_zeroes)
        {
            output.push_back(*start);
            ++zero_count;
        }
        ++start;
    }
}

你可以使这个方法更通用。更改int为typename ValueType和0，ValueType value_to_remove您正在std::algorithm达到通用水平...

于 2013-01-15T19:08:25.077 回答
0

这是用于任意类型的 C++11 版本（使用auto、lambda 和移动语义）：std::vectorvalueT

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>

template<std::size_t N, typename T>
std::vector<T> collapse_consecutive(std::vector<T> v, T const& value)
{
    if (v.size() <= N) return v;

    for (auto it = v.begin(); it != std::prev(v.end(), N); ++it) {
        if (*it == value) {
            // find first following mismatch
            auto jt = std::find_if(it, v.end(), [&](T const& elem) {               
               return elem != value;
            });
            // keep first N matches, remove rest of matches
            if (std::distance(std::next(it, N), jt) > 0)               
                v.erase(std::remove(std::next(it, N), jt, value), jt);
        }
    }
    std::for_each(v.begin(), v.end(), [](int const& elem) { std::cout << elem << ", "; });
    std::cout << "\n";
    return v;
}

int main()
{
   std::vector<int> v = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8};

  collapse_consecutive<0>(v, 0);
  collapse_consecutive<1>(v, 0);
  collapse_consecutive<2>(v, 0);
  collapse_consecutive<3>(v, 0);
  collapse_consecutive<4>(v, 0);
  collapse_consecutive<5>(v, 0);  
}

LiveWorkSpace上的输出

stdout: 
7, 12, 2, 27, 10, 8, 
7, 0, 12, 0, 2, 0, 27, 10, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 27, 10, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8,
于 2013-01-15T20:03:45.287 回答
0

您可以通过将仿函数传递给 list::remove_if 来实现。下面的例子。

#include <iostream>
#include <list>

std::list<int> origL{7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8};

template <typename T>
struct remove_more_than_n_consecutive_zeros
{
    int n;
    int i;
    F(int n) : n(n), i(0) { }

    bool operator()(const T &element) {
        if (0 == element) {
            ++i;
            return i > n;
        }
        else 
        {
            i = 0;
            return false;
        }
    }
};

int main()
{
    for (int i = 0; i < 5; ++i) {
        std::list<int> L = origL;
        L.remove_if(remove_more_than_n_consecutive_zeros<int>(i));
        for (int x : L) { std::cout << x << " "; }
        std::cout << std::endl;
    }
}
于 2013-01-15T19:12:19.567 回答
0

它本质上是一个状态机，所以你可以用 std::regex 做一些聪明的事情，但这里有一个简单的实现。

void TrimConsecutiveValues(int value, int cKeep, std::list<int> &list) {
  int cSeen = 0;
  auto it = list.begin();
  while (it != list.end()) {
    if (*it == value) {
      if (cSeen < cKeep) {
        ++cSeen;
        ++it;
      } else {
        it = list.erase(it);
      }
    } else {
      cSeen = 0;
      ++it;
    }
  }
}
于 2013-01-15T19:20:37.380 回答