Алгоритм — Как в 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 ++.
Любая помощь будет искренне оценена.
Решение
Вот некоторый код, который должен делать эту работу:
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;
}
Другие решения
Для случая 0 вы можете использовать std::remove, а для случая 1 вы можете использовать std::unique с предикатом, который применяется только к 0, Для больших значений либо разработайте подлый предикат с сохранением состояния для использования с unique или позаимствовать его логику, чтобы применить к большим последовательностям.
Самый простой способ — вернуть 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 уровень универсальности …
Вы можете сделать это, передав функтор 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;
}
}
Вот версия 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,
По сути, это конечный автомат, так что вы могли бы сделать что-то умное с 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;
}
}
}
detector