JuniorКодЧастоЕщё не отвечали
URLify: замена пробелов на %20 на месте
Замените каждый пробел в символьном буфере на %20, редактируя буфер на месте. Буфер заранее достаточного размера для более длинного результата (без реаллокации); вам дана истинная длина текста в нём.
Требования:
- O(n) время, O(1) дополнительной памяти.
// buf вмещает расширенный результат; trueLen — длина текста
void urlify(char* buf, int trueLen) {
// ваш код здесь
}Допишите реализацию.
Два прохода. Сначала посчитайте пробелы, чтобы вычислить итоговую длину. Затем пишите с конца: копируйте каждый символ в его финальную ячейку, а для каждого пробела пишите '0', '2', '%' (в обратном порядке). Запись справа налево гарантирует, что вы не затрёте необработанный вход. O(n) время, O(1) дополнительной памяти.
- ✗Писать с начала и затирать ещё не обработанные символы
- ✗Не использовать предусмотренную ёмкость и писать за исходной длиной
- ✗Выводить символы
%20в неверном порядке при обратном проходе
- →Почему запись с конца избегает затирания непрочитанных символов?
- →Как изменилось бы решение, если буфер нельзя менять на месте?
Оглавление
Задача
Замените пробелы на %20 на месте в предварительно увеличенном буфере за O(n) и O(1) памяти.
Решение
#include <cstring>
void urlify(char* buf, int trueLen) {
int spaces = 0;
for (int i = 0; i < trueLen; ++i)
if (buf[i] == ' ') ++spaces;
int write = trueLen + spaces * 2 - 1; // последняя ячейка результата
for (int read = trueLen - 1; read >= 0; --read) {
if (buf[read] == ' ') { // пишем "%20" задом наперёд
buf[write--] = '0';
buf[write--] = '2';
buf[write--] = '%';
} else {
buf[write--] = buf[read];
}
}
}Ключевые моменты
- Первый проход считает пробелы и вычисляет финальную длину.
- Запись с конца не затирает ещё не прочитанные символы.
%20пишется в обратном порядке (0,2,%), так как мы движемся справа налево.
Оглавление
