Вопрос:
Для каждого запуска x или более последовательных нулей в списке в С++ я хотел бы удалить все нули в прогоне, за исключением x из них. Если x = 0, то удалите все нули.
Я думал о С++-функции, в которой в качестве входных данных был выбран список 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 (qaru.site/questions/1425964/…) и получил отличные ответы. Теперь я хотел бы выполнить эту задачу на С++.
Любая помощь будет искренне оценена.
Лучший ответ:
Вот код, который должен выполнить задание:
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++ ish, но я нахожу более ясным манипулирование значениями напрямую и не включает новый тип данных (a struct для отслеживания числа 0, с которым вы столкнулись).
Причина, по которой код не работает с использованием NTL::ZZ, заключается просто в том, что не существует неявного преобразования между большим числом int, 0 и a 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; } Ответ №1
В случае 0 вы можете использовать std::remove, а для случая 1 вы можете использовать std::unique с предикатом, который применит только к 0. Для больших значений либо создайте скрытый предикат состояния для использования с unique, либо заимствуйте его логику для применения к более крупным последовательностям.
Ответ №2
Самый простой способ – вернуть 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 уровню родовости…
Ответ №3
Вы можете сделать, передав функтор в список:: 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; } } Ответ №4
Это, по сути, машина состояния, поэтому вы, вероятно, можете сделать что-то умное с помощью 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; } } } Ответ №5
Вот версия С++ 11 (используя auto, lambdas и семантику перемещения), которая использует 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,
