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

Почему это правда? Есть много ответов на вопрос, почему решение алгоритмов делает вас лучшим разработчиком, но самый простой способ решить эту проблему - заявить правду. По правде говоря, алгоритм - это всего лишь причудливое слово для обозначения процедуры. Другими словами, это просто список (иногда тот, который нужно повторить перед завершением) серии шагов, которые компьютер выполняет для выполнения задачи. Таким образом, если вы можете кодировать процедуру для получения результата, это упрощает применение ваших шаблонов в ваших процедурах для кодирования проектов, что упрощает написание лучшего кода.

Все еще слишком сложно? Подумайте об этом так: инструкции коробки для смешивания торта считаются алгоритмом.

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

Недавно на этой неделе я решил ряд задач, связанных с алгоритмами, но, чтобы внести свой вклад, чтобы помочь сообществу программистов понять концепцию решения алгоритмов, я выберу одну, а затем объясню, каким был мой мыслительный процесс при решении алгоритмов. . Затем, используя тестовый пример, чтобы объяснить это на более глубоком уровне. Решение этой проблемы кодирования будет написано на JavaScript.

Алгоритм проверки подпоследовательности

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

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

[2, 3, 5]

являются подпоследовательностью массива:

[1, 2, 3, 4, 5]

Обратите внимание, что одно число в массиве и сам массив являются допустимыми подпоследовательностями массива.

Пример ввода (что входит в аргумент): array = [5, 1, 22, 25, 6, -1, 8, 10]

последовательность = [1, 2, -1, 10]

Пример вывода (пример того, что должно получиться в процессе работы алгоритма): true

Шаг 1. Задайте себе несколько важных вопросов о том, как будет выглядеть решение на основе полученных результатов

Моя первая мысль, пытаясь решить эту проблему, - это спросить себя: «Как лучше всего получить истинный или ложный результат из функции?» Следующей моей мыслью, чтобы ответить на свой вопрос, было, конечно, использовать оператор if, поэтому в тот момент я знал, что мне понадобится оператор if где-нибудь в моем решении.

Затем я подумал: «Как мне просмотреть массив, чтобы узнать, истинно ли условие?» Было бы использовать цикл для итерации (просмотра) всех чисел, которые они дают мне в основном массиве. Есть много способов итерации с помощью JavaScript, например, использование цикла while, цикла for и цикла for of. Я выбрал цикл for, потому что, на мой взгляд, индексы легче отслеживать.

Шаг 2. Создайте код для своей основной структуры, чтобы все было скреплено соответствующими аргументами

С этими двумя мыслями в голове у меня была основная структура моего решения алгоритма. Я начал с ключевого слова function, дал функции подходящее имя и передал два аргумента, о которых они говорили в вопросе:

function isValidSubsequence(array, sequence) {

}

Шаг 3. Закодируйте то, что находится внутри основной структуры, на основе шага 1. Примечание. При необходимости повторите шаг 1.

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

function isValidSubsequence(array, sequence) {
   for(i=0;
}

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

function isValidSubsequence(array, sequence) {
   for(i=0; i < array.length;
}

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

function isValidSubsequence(array, sequence) {
   for(i=0; i < array.length; i++){

Теперь мне нужен оператор if, чтобы увидеть, равен ли текущий номер в массиве текущему порядковому номеру в массиве последовательностей. Если бы оно было равно, мне нужен был способ перейти к следующему числу в моем массиве последовательностей, чтобы проверить это следующее число. Вот почему я установил новую переменную с именем j, чтобы она была установлена ​​равной 0, как и переменная счетчика основного массива в качестве отправной точки. Состояние в конечном итоге выглядело следующим образом вместе с моими полезными комментариями.

function isValidSubsequence(array, sequence) {
   let j = 0 //set a variable equal to j, this represents the index      of the sequence array
   for(i=0; i < array.length; i++){
//if the number we are on in the first array matches the number we are on in the second array then add 1 to the variable j 
   if (array[i] === sequence[j]) {
         j++
//Add 1 to j
      }
   }
}

Шаг 4. В какой-то момент найдите способ конкретно завершить решение алгоритма, вернув запрошенные выходные данные.

На этом этапе цикл for будет запускаться снова и снова, проверяя, совпадают ли числа для каждого числа из каждого массива. Теперь я подумал про себя: «Должен быть какой-то способ вернуть истину или ложь с помощью оператора if после завершения этого цикла». Поэтому я решил написать оператор if, который говорит, что если индекс массива последовательностей равен длине последовательности его массива, то возвращать true; в противном случае верните false.

function isValidSubsequence(array, sequence) {
   let j = 0 //set a variable equal to j, this represents the index      of the sequence array
   for(i=0; i < array.length; i++){
   //if the number we are on in the first array matches the number  we are on in the second array then add 1 to the variable j 
   if (array[i] === sequence[j]) {
         j++
//Add 1 to j
      }
   }
  if (j === sequence.length) {
//if the final index of the sequence array is equal to the sequence's length then return true
  return true
 } else {
//in all other cases return false
  return false
 }
}

Я закодировал это таким образом, потому что, как только будет обнаружено, что полная последовательность соответствует основному массиву после того, как конечный индекс последовательности совпадает с количеством элементов (длиной) в последовательности, тогда верно, что последовательность существует в основном массиве . С другой стороны, если не все числа в последовательности соответствуют какой-то части основного массива, тогда j не будет увеличиваться, как показано в нашем цикле for. Помните, что j может увеличиваться только в том случае, если номер основного массива совпадает с номером последовательности. Поэтому во всех остальных случаях функция вернет false.

Это конец моего алгоритма.

Применение на практике - пример тестового случая

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

Ввод тестового примера: массив = [1, 1, 6, 1] и последовательность = [1, 1, 1, 6]

Вывод тестового примера: false

Итак, мы идем:

1 function isValidSubsequence(array, sequence) {
 2 let j=0
 3 for(i=0; i < array.length; i++){
 
 4 if (array[i] === sequence[j]) {
 5 j++
 6 }
 7 }
 8 if (j === sequence.length) {
 9   return true
 10 } else {
    11 return false
 12 }
13 }

В первый раз, когда это происходит, мы начинаем с 1 на 0-м месте (представленном i) в основном массиве и с 1 на 0-м месте (представленном j) в массиве последовательностей.

В строке 4, если число, которое мы проверяем, в данном случае 1, равно числу, которое мы проверяем в другом массиве, также в этом случае 1, затем увеличиваем j. J теперь равно 1, а i всегда увеличивается на 1, пока цикл for проходит еще один раунд, поэтому теперь i = 1. (i = 1, j = 1)

Цикл for повторяется до тех пор, пока не пройдут все числа в основном массиве. Он повторяется, пропуская строки с 3 по 7.

Во второй раз, когда это происходит, мы снова начинаем с 1 на 1-м месте (снова обозначается i) в основном массиве и 1 на 1-м месте (снова обозначается j) в массиве последовательностей. И снова числа, которые мы проверяем, равны друг другу, поэтому теперь j и i снова увеличиваются. (я = 2, j = 2)

Теперь обстоятельства изменятся в 3-м раунде: 6 в основном массиве будут сравниваться с 1 в массиве последовательностей. На этот раз j не будет увеличиваться, потому что наше условие ложно, но переменная i все равно будет увеличиваться. (я = 3, j = 2)

Цикл for запускается еще раз и снова не будет увеличивать j, поэтому теперь у нас технически будет i = 4 против j = 2. Цикл for завершается, потому что все элементы в массиве были проверены, и теперь код выполняется в строке 8.

8 if (j === sequence.length) {
 9   return true
 10 } else {
    11 return false
 12 }
13 }

Последняя проверка утверждает, что если j равно длине последовательности в массиве, возвращается истина. Мы знаем, что 2, представляющее j, не равно 3, что является длиной массива последовательности, отсчитываемой от 0, как это делают компьютеры. Итак, этот пример тестового случая возвращает false в строке 11.

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

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

Я очень рекомендую, если вы сами хотите стать лучше в алгоритмах, попробовать Algoexpert.io. Я знаю, что вы, наверное, видели дрянную рекламу на YouTube, но этот сайт действительно помогает упростить изучение алгоритмов благодаря красивому интерфейсу. Удачного решения алгоритма и приготовления торта :)