JuniorКодЧастоЕщё не отвечали
Схлопывание серий пробелов в один пробел на месте
Схлопните каждую серию подряд идущих пробелов в изменяемой строке до одного пробела. Не обрезайте пробелы в начале и в конце — только схлопывайте серии (так "some string " станет "some string ").
Требования:
- O(n) время, O(1) дополнительной памяти — правьте на месте и усекайте.
void normalizeSpaces(std::string& s) {
// ваш код здесь
}Допишите реализацию.
Используйте индексы чтения и записи. Копируйте каждый символ в позицию записи, но пишите пробел, только если предыдущий записанный символ не был пробелом. После прохода усеките строку до индекса записи. Один проход, O(n) время, O(1) дополнительной памяти; одиночные пробелы в начале и в конце сохраняются.
- ✗Обрезать пробелы в начале или конце, когда по условию надо только схлопывать серии
- ✗Забывать усечь строку, оставляя устаревшие символы в хвосте
- ✗Вызывать
eraseна каждый лишний пробел, превращая O(n) в O(n²)
- →Как одиночный конечный пробел сохраняется, если вход заканчивается несколькими?
- →Что меняется, если нужно ещё и обрезать концы?
Оглавление
Задача
Схлопните серии пробелов в один пробел на месте за O(n) и O(1) памяти, не обрезая края.
Решение
#include <string>
void normalizeSpaces(std::string& s) {
size_t write = 0;
for (size_t read = 0; read < s.size(); ++read) {
bool isSpace = s[read] == ' ';
bool prevSpace = write > 0 && s[write - 1] == ' ';
if (isSpace && prevSpace) continue; // пропускаем лишний пробел
s[write++] = s[read];
}
s.resize(write); // усекаем хвост
}Ключевые моменты
- Пробел записывается, только если предыдущий записанный символ — не пробел.
- Края не обрезаются: одиночный пробел в начале/конце проходит.
resize(write)убирает оставшийся хвост; всё за один проход O(n).
Оглавление
