Пока я готовлюсь к техническим собеседованиям, на этой неделе я продолжил изучение популярной техники двух указателей для выполнения операций на месте.

Почему алгоритмы на месте так популярны? Потому что они могут помочь нам сэкономить время и место.

Возьмем, к примеру, следующий метод. Этот алгоритм на месте позволяет избежать затрат на инициализацию или необходимость копирования массива в новый массив со значениями в квадрате или выделения дополнительного пространства для хранения новых значений в квадрате. Вместо этого с помощью решения на месте мы можем просто возвести в квадрат И переназначить каждый элемент во время итерации по массиву.

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]

Как и в предыдущем примере, здесь я использовал систему с двумя указателями, чтобы найти решение на месте. Хотя формулировка отличается, задача та же. Нам нужно а) выполнить итерацию по массиву, чтобы найти что-то, что либо соответствует условию, либо нет, а затем нам нужно б) в том же массиве разделить или создать своего рода разделение между элементами, чтобы иметь возможность выбирать только что нужно.

Для подобных проблем метод двух указателей может обеспечить быстрое и эффективное решение на месте. Рассмотрите возможность его использования!

Спасибо за чтение!