Держите свои основы информатики в совершенстве на этом занятии Pomodoro.
Вопрос о проверке подпоследовательности - простая задача, но вводит важную концепцию последовательности, в которой порядок имеет значение. Это можно сравнить с поиском подмножества массива, в котором порядок не имеет значения. В этой статье мы разберемся с вопросом о подпоследовательности, напишем тесты и, наконец, разработаем решение вместе с его большими временными и пространственными сложностями.
Кодирование Pomodoro начинается прямо сейчас!
Примечание. В этой статье предполагается, что вы знаете, как настроить рабочее пространство Go и установить зависимости программы.
Понять проблему
Проверка подпоследовательности включает ввод двух отдельных массивов. Один из массивов - это последовательность, а другой массив - это набор значений, которые могут содержать или не содержать эту последовательность. Для начала всегда полезно написать несколько примеров:
Example #1 array = [1,0,1] sequence = [1] result: true Example #2 array = [1,5,9] sequence = [9,5] result: false Example #3 array = [1,4,-1,6,4,9,10] sequence = [1,-1,10] result: true
Какие еще примеры базовых случаев вы можете придумать?
Написание тестов на основе таблиц в Go
Популярность разработки через тестирование (TDD) растет, поскольку она заставляет вас писать минимальный код, который подвергается тщательному тестированию. Я обнаружил, что один из лучших способов улучшить свои навыки TDD - это начать с таких проблем программирования, как эти, прежде чем переходить к более стандартным ситуациям разработки программного обеспечения. К счастью, в Go есть фантастическая встроенная поддержка тестирования.
После импорта пакетов assert и testing мы создаем функцию TestValidateSubsequence(), которая принимает указатель на объект testing.T. Оттуда мы можем инициировать массив структур в качестве наших тестовых примеров с четырьмя полями для описания каждого теста. Мы определяем шесть общих структур, чтобы охватить основные случаи проверки подпоследовательности, можете ли вы еще что-нибудь придумать?
После того, как мы определим наш массив структур, которые будут действовать как тестовые примеры, мы объявляем цикл for, который будет перемещаться по ним. Мы получаем индивидуальный тестовый пример, а затем вызываем t.Run(), чтобы вызвать пакет тестирования Go. Мы также можем вызвать t.Parallel() изнутри для повышения производительности (просто для выработки хороших привычек). Затем мы получаем результат нашей ValidateSubsequence() функции (которая будет реализована следующей), передавая ему inputArray и inputSequence текущего тестового примера. Наконец, мы утверждаем, совпадает ли результат нашей функции с тем, что мы ожидаем от тестового примера.
У Go самый элегантный и упрощенный подход к тестированию среди всех языков, передумаю.
Решение - O (N) времени и O (1) Space
Я предлагаю только одно решение, потому что существует не так много способов решить эту проблему, не усложняя ее. Вы не можете использовать цикл double for для выполнения проверки подпоследовательности методом грубой силы - это было бы правильным решением для поиска действительного подмножества и потребовало бы времени O (N²).
В любом случае решение этой проблемы короткое, но его можно использовать для более сложных задач, когда вам нужно найти или проверить подпоследовательность. По сути, мы хотим отслеживать, видели ли мы каждый элемент в последовательности, прежде чем перейти к следующему элементу. Если мы находим элемент последовательности в массиве, мы можем перейти к следующему элементу последовательности, отслеживая, где мы находимся в массиве.
Итак, сначала мы инициализируем индекс для массива, а также для последовательности. Затем мы запускаем цикл, который завершается, если какой-либо индекс выходит за пределы соответствующего массива. Наша первая проверка - увидеть, равен ли текущий элемент массива текущему элементу последовательности. Если это так, то мы нашли совпадение элемента последовательности и можем увеличить наш индекс последовательности. Независимо от того, находим мы совпадение или нет, мы должны увеличивать индекс массива, чтобы продолжить наш поиск.
После завершения цикла мы возвращаем логическое значение, указывающее, совпадает ли индекс последовательности с длиной исходной последовательности. Мы делаем это, потому что это может быть правдой только в том случае, если мы найдем соответствие по порядку для каждого элемента последовательности, чтобы мы увеличили индекс последовательности до длины самой последовательности.
Время работы этого алгоритма ограничено длиной array. Это связано с тем, что последовательность увеличивается только при совпадении, в то время как мы всегда будем увеличивать индекс array. Даже если последовательность длиннее, чем массив, мы остановимся, когда индекс массива станет слишком большим. Таким образом, наша временная сложность равна O (N), где N - длина array. Сложность пространства - это постоянная величина O (1), потому что мы не храним никаких дополнительных структур данных.
Надеюсь, вам понравилось читать эту статью и вы узнали что-то новое. Если вы нашли какие-либо части особенно полезными или хотели бы получить руководства по любым другим проблемам с кодированием, я рекомендую вам оставить комментарий ниже! Спасибо за прочтение.
