Подход Leetcode к алгоритмам и структурам данных.
Фото Маркуса Списке на Unsplash
Всегда думайте о программировании как о решении головоломок, а когда дело доходит до головоломок, игра с палиндромами как концепцией может помочь вам взбодрить свой ум и сохранить мышцы программирования в форме. В этой статье сначала будет определена концепция, а затем использован подход leetcode для понимания концепции. Цель состоит в том, чтобы вы не только поняли концепцию, но и подготовились к любой реализации концепции в будущем.
Определение. Палиндром — это фраза, которая одинаково читается вперед и назад.
Виола! вот и все. Позвольте мне привести вам несколько примеров, которые помогут вам понять эту концепцию.
Подумайте о таких словах, как «мадам», «радар» и «отправить», которые, если их поменять местами, будут читаться одинаково. Это может быть расширено до более длинных фраз, таких как «Мадам, я Адам» или «Не кивайте», где, если вы не включаете пробелы, перевернутая форма всех букв будет такой же, как и передняя.
Теперь давайте посмотрим на leetcode 125. Допустимая проблема с палиндромом
leetcode # 125 описание проблемы
Подход
Если вы не читали формулировку задачи, я настоятельно рекомендую вам прочитать ее еще раз, потому что это самый важный шаг. Возможно, вы захотите просто перевернуть строку и сравнить ее с оригиналом, но этот подход не сработает. Существует ограничение, согласно которому мы не должны учитывать в нашем анализе небуквенно-цифровые элементы. Буквенно-цифровые элементы включают все цифры и алфавиты (как прописные, так и строчные). Это означает, что все небуквенно-цифровые элементы будут включать специальные символы, такие как «‘.\{}()-=» и т. д.
Логика
Следовательно, более осторожным подходом было бы запустить два указателя слева и справа, двигаясь друг к другу, и продолжать пропускать небуквенно-цифровые символы, пока не найдете два допустимых элемента. Сравните эти два элемента, чтобы увидеть, одинаковы ли они, если не возвращают false, если одинаковы, то продолжайте процесс, пока указатели не пересекутся.
Давайте дадим этому подходу более конкретную реализацию с использованием C++. Единственным дополнением к приведенному выше псевдокоду является добавление проверки не буквенно-цифровых символов. Позвольте мне показать вам на примере.
Поняв этот незначительный случай, наконец, вот код.
Это только самые основные проблемы, связанные с палиндромами, но они должны дать вам хорошее понимание концепции. Это действительно так же просто, как найти фразу, которая будет одинаково интерпретироваться вперед и назад. Приведенная выше реализация также называется «подход с двумя указателями». Этот алгоритм имеет временную сложность O(n), что означает, что он может достичь желаемого результата за один проход полной фразы. Я постараюсь более подробно остановиться на обоих этих аспектах в другой статье, так как она будет слишком длинной, чтобы поместиться здесь.
И, наконец, постарайтесь не вспоминать этот вопрос, а только концепцию палиндрома и идею атаки на проблему с обеих сторон с помощью указателей. Программирование — это поистине захватывающее и волшебное путешествие, если вы сохраняете радость обучения!
