Пока я готовлюсь к техническим собеседованиям, на этой неделе я продолжил изучение популярной техники двух указателей для выполнения операций на месте.
Почему алгоритмы на месте так популярны? Потому что они могут помочь нам сэкономить время и место.
Возьмем, к примеру, следующий метод. Этот алгоритм на месте позволяет избежать затрат на инициализацию или необходимость копирования массива в новый массив со значениями в квадрате или выделения дополнительного пространства для хранения новых значений в квадрате. Вместо этого с помощью решения на месте мы можем просто возвести в квадрат И переназначить каждый элемент во время итерации по массиву.
function squareInPlace(arr) {
arr.forEach((int, index) => {
arr[index] *= int;
});
// NOTE: no need to return anything - we modified arr in place
}
Имея это в виду, учитывая следующий пример, найденный на Interview Cake, как мы можем перевернуть список слов на месте?
В: Вы работаете в секретной команде, занимающейся закодированными передачами.
Ваша команда пытается расшифровать недавнее сообщение, опасаясь, что это заговор с целью взлома крупного европейского национального хранилища тортов. Сообщение в основном расшифровано, но все слова задом наперед! Ваши коллеги передали последний шаг вам.
Напишите функцию reverseWords(), которая принимает сообщение как массив [строк] и меняет порядок слов на месте.
let arr = ["!", "cake", "that", "me", "give"]; function reverseWords(arr) { let counter = 0; for (let i = arr.length - 1; i >= counter; i--) { let tempVar = arr[i]; arr[i] = arr[counter]; arr[counter] = tempVar; counter++; } return arr; } function reverseWords(arr) --> ["give", "me", "that", "cake", "!"]
Используя систему с двумя указателями, один указатель помогает нам отслеживать значения, которые нужно поменять местами, в то время как другой указатель отслеживает значения, с которыми они будут заменены. Давайте разберем это:
Я начал свою итерацию в конце массива, однако вы, безусловно, можете начать итерацию в начале. Сначала я определил переменную с пометкой counter, которую я установил на ноль; counter отметит индекс элемента, заменив соответствующее значение i. Затем я определил цикл for. Цикл for будет продолжать работать, пока i ›= counter. После каждой итерации iуменьшается на 1 и count увеличивается на 1, встречаясь в середине index[2] или "that", где мой цикл for заканчивается.
Давайте посмотрим, что происходит внутри цикла:
- Сначала я объявляю временную локальную переменную, чтобы отслеживать значения, которыми я обмениваю i с
- Затем я заменяю arr[i] на arr[counter]
- Затем я заменяю arr[counter] ранее объявленной временной переменной.
- Наконец, я увеличиваю свою переменную-счетчик на 1 для каждого нового прохода цикла.
Как только я закончу цикл for, я возвращаю arr, помните, что эта проблема требует локального или деструктивного решения, что означает, что мы можем просто вернуть измененный массив.
Приведенное выше решение приводит к идеальному дополнительному пространству O (1) и времени O (n). Поэтому такие операции предпочтительнее неразрушающих или неуместных алгоритмов.
Аналогичный пример (LeetCode), для которого метод двух указателей помогает нам найти решение на месте:
Вопрос. Учитывая массив nums и значение val, удалите все экземпляры этого значения на месте и верните новую длину.
Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, модифицируя входной массив на месте с O(1) дополнительной памяти.
Порядок элементов можно изменить. Неважно, что вы оставите за пределами новой длины.
Input: nums = [3,2,2,3], val = 3 function removeElement(nums, val) { let count = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] !== val) { let temp = nums[count]; nums[count] = nums[i]; nums[i] = temp; count++; } } return count; } Output: 2, nums = [2,2]
Как и в предыдущем примере, здесь я использовал систему с двумя указателями, чтобы найти решение на месте. Хотя формулировка отличается, задача та же. Нам нужно а) выполнить итерацию по массиву, чтобы найти что-то, что либо соответствует условию, либо нет, а затем нам нужно б) в том же массиве разделить или создать своего рода разделение между элементами, чтобы иметь возможность выбирать только что нужно.
Для подобных проблем метод двух указателей может обеспечить быстрое и эффективное решение на месте. Рассмотрите возможность его использования!
Спасибо за чтение!