Готовясь к собеседованиям, я довольно много практиковал свои навыки работы с алгоритмами на LeetCode и других сайтах. Прочтите пошаговое руководство по моему JavaScript-решению задачи Build an Array With Stack Operations на LeetCode.

Проблема

Дан массив target и целое число n. На каждой итерации вы будете считывать число из list = {1,2,3..., n}.

Создайте массив target, используя следующие операции:

  • Отправить: прочитать новый элемент с начала list и поместить его в массив.
  • Pop: удалить последний элемент массива.
  • Если целевой массив уже построен, прекратите чтение дополнительных элементов.

Вам гарантируется, что целевой массив строго увеличивается и содержит только числа от 1 до n включительно.

Верните операции для построения целевого массива. Вы гарантируете, что ответ уникален.

Ограничения:

  • 1 <= target.length <= 100
  • 1 <= target[i] <= 100
  • 1 <= n <= 100
  • target строго возрастает.

Пример 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

Пример 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Пример 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.

Пример 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]

Решение

Для начала давайте создадим пустой массив с именем result для хранения информации push и pop, которую мы в конечном итоге будем возвращать по мере сбора дополнительной информации из нашего целевого массива. Из ограничений задачи мы знаем, что целевой массив содержит только числа от 1 до n, и мы знаем, что n больше или равно 1. Используя эту информацию, мы можем выяснить, как заполнить результирующий массив, создав отдельный числовая переменная num, начинающаяся с 1. Мы будем продолжать цикл до тех пор, пока num не станет больше n, каждый раз увеличивая num, что помогает нам избежать ужасного бесконечного цикла. Мы также собираемся создать другую переменную i, которая поможет нам отслеживать элемент целевого массива по мере его перемещения.

Пока это то, что мы имеем!

let result = [];
let i = 0;
let num = 1;
while (num <= n) {
   ...
   num++;
}

В нашем цикле while нам нужны условные операторы для обработки трех случаев. Наш первый случай — если мы достигнем конца целевого массива до того, как значение num совпадет со значением n. Мы можем определить это по значению i. Если i равно target.length, мы знаем, что прошли все значения target, и если это произойдет, мы можем выйти из цикла и вернуть наш массив результатов, не продолжая увеличивать num.

Наш второй случай — если текущее значение целевого массива равно текущему значению num. Это будет означать, что текущее значение num существует в этом массиве, и для создания цели мы должны добавить «Push» в наш массив результатов. В этом случае мы также переместим i к следующему элементу target, чтобы найти следующее значение num, соответствующее i.

Наш третий случай — все остальное. Если текущее значение num не существует в target, нам нужно сначала добавить «Push» к результату, а затем добавить «Pop», чтобы указать, что мы не будем сохранять его в нашем воссоздании массива.

Если мы еще не просмотрели весь наш целевой массив, но значение num теперь больше n, мы можем выйти из цикла и, наконец, вернуть результат в качестве последнего шага нашей функции.

И все готово! Давайте проверим полное решение ниже, в среде выполнения O (n).

Вы можете найти эту задачу на LeetCode — попробуйте!

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