Что делает “оперативный” средний?
Обратные слова в строке (слова разделяются одними или несколькими пробелами). Теперь сделайте это оперативный.
Что делает оперативный средний?
3 ответа
In-place означает, что вы должны обновить исходную строку, а не создавать новую.
В зависимости от языка/фреймворка, который вы используете, это может быть невозможно. (Например, строки неизменяемы в .NET и Java, поэтому невозможно выполнить обновление строки на месте, не прибегая к каким-то злобным хакам)
.Вы должны изменить содержимое исходной строки на обратное, не используя временную переменную хранения для хранения строки.
In-place алгоритмы могут использовать только O(1) дополнительного пространства, по существу. Обратное преобразование массива (по сути, то, к чему сводится вопрос на собеседовании) является классическим примером. Следующий пример взят из Википедии:
Предположим, мы хотим развернуть массив из n элементов. Один простой способ сделать это:
function reverse(a[0..n]) распределить b[0..n] для i от 0 до n b[n - i] = a[i] return bК сожалению, это требует
O(n)дополнительного места для создания массиваb, а выделение часто является медленной операцией. Если нам больше не нуженa, мы можем заменить его своим собственным реверсом, используя этот алгоритм in-place:function reverse-in-place(a[0..n]) for i from 0 to floor(n/2) swap(a[i], a[n-i])
Иногда сделать что-то на месте ОЧЕНЬ сложно. Классический пример - общее транспонирование неквадратной матрицы.