Главная » C++ » Алгоритм - Как в C ++ удалить все нули, кроме x из них, при каждом запуске последовательных нулей в списке?

Алгоритм — Как в C ++ удалить все нули, кроме x из них, при каждом запуске последовательных нулей в списке?

За каждый прогон x или более последовательных нулей в списке в C ++, я хотел бы удалить все нули в прогоне, кроме 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 ++.

Любая помощь будет искренне оценена.

3

Решение

Вот некоторый код, который должен делать эту работу:

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 просто не существует неявного преобразования между int, 0и NTL::ZZ большое число, поэтому оно не может remove(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;
}
5

Другие решения

Для случая 0 вы можете использовать std::remove, а для случая 1 вы можете использовать std::unique с предикатом, который применяется только к 0, Для больших значений либо разработайте подлый предикат с сохранением состояния для использования с unique или позаимствовать его логику, чтобы применить к большим последовательностям.

1

Самый простой способ — вернуть std::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 уровень универсальности …

1

Вы можете сделать это, передав функтор 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;
}
}
0

Вот версия C ++ 11 (используя auto, лямбды и семантика перемещения) std::vector для произвольного value типа T:

#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,
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;
}
}
}
0
Источник
По вопросам рекламы [email protected]
Web-Answers © 2024 Наверх