AA1

Задача:

В заданной строке заменить подряд идущие пробелы на один пробел.

Примечание:

Будем называть строку правильной, если она не содержит подряд идущих пробелов.

Тестирование:

 Исходная строка  Оптимистичное ожидание Комментарий
Gagarin               became an                     international celebrity, and was                                              awarded many                     medals and titles, including                       Hero of the                        Soviet Union. Gagarin became an international celebrity, and was awarded many medals and titles, including Hero of the Soviet Union.  Пройден.
 Leonardo                             was, and                             is,                                         renowned                               primarily                         as a                             painter. Leonardo was, and is, renowned primarily as a painter.  Пройден.

Код на С++

Код на Java

 

Пояснение:

Вариант удаления пробелов с помощью [latex]erase()[/latex] является самым очевидным. Но у него больше недостатков, чем достоинств. Данный метод имеет линейную асимптотику, в худшем случае он выполнил бы [latex]n — 1[/latex] ( в дальнейшем [latex]»n»[/latex] — это длина строки ) сдвиг в индексах строки.

Другой способ — создание новой строки и добавление туда только нужных нам символов. Единственная проблема — новая строка, т. е. в худшем случае у нас появится строка равная данной или же на один символ меньше (если была добавлена проверка на правильность строки).

Второй способ мне нравится больше (просто потому, что он работает), но выделять новую строку очень не хочется. Оказалось, что можно обойтись и без неё. В качестве новой я использовал исходную. Для этого ввел два «указателя» на позиции элементов. Первый пробегает всю строку в цикле, второй же указывает на элемент, этой строки, в который будет положено новое значение. Таким образом, полученная последовательность символов (от нулевой, до [latex]j[/latex] — той не включительно) будет правильной строкой. Осталось удалить элементы на полуинтервале от [latex]j[/latex] до [latex]n[/latex].

 

Related Images: